Inducción sobre número combinatorio

Hay nuevos comentarios sin leer

El problema de la semana es una consulta que hace unos días me envió Gustavo al mail del blog. Os lo dejo aquí:

Demostrar por inducción que:
$\displaystyle{\sum_{k=0}^n {n \choose k} =2^n}$

Ánimo y a por él.

Posts aleatorios

Autor: ^DiAmOnD^ | Publicado el 15 de July de 2008
Categorías: Juegos | Imprime este post

Sin comentarios

Javier | 15 de July de 2008 | 10:06

Deduzco que sera demostrar

$\displaystyle \sum_{k=0}^n {n \choose k}=2^n$
vengoroso | 15 de July de 2008 | 11:00

¿Por qué por inducción? Con lo bonito que es el binomio de Newton…
Javier | 15 de July de 2008 | 11:16

$\displaystyle {0 \choose 0}=\frac{0!}{0!0!}=1$

Supongamos

$\displaystyle \sum_{k=0}^n {n \choose k}=2^n$

entonces hay que demostrar que

$\displaystyle \sum_{k=0}^{n+1} {{n+1} \choose k}=2^{n+1}$

$\displaystyle {{n+1} \choose 0}=\frac{(n+1)!}{0!(n+1)!}=1={{n} \choose 0}$

$\displaystyle {{n+1} \choose {n+1}}=\frac{(n+1)!}{(n+1)!0!}=1={{n} \choose n}$

Demostramos que $\displaystyle {{n+1} \choose k}={{n} \choose {k-1}}+{{n} \choose k}$ $\forall k \in (1,2,\cdots,n)$

$\displaystyle {{n} \choose {k-1}}+{{n} \choose k}= \frac{n!}{(k-1)!(n-(k-1))!}+ \frac{n!}{(k)!(n-k)!} =$

$\displaystyle \frac{n!k}{(k)!(n-k))!(n+1-k)}+ \frac{n!}{(k)!(n-k)!} = \frac{n!}{(k)!(n-k)!} (1+\frac{k}{n+1-k}) = \frac{n!}{(k)!(n-k)!} (\frac{n+1}{n+1-k}) = \frac{(n+1)!}{(k)!(n+1-k)!}$

Con lo que hemos demostrado que cualquier termino de la suma $\displaystyle \sum_{k=0}^n {n \choose k}$ esta dos veces en la suma desarrollada de $\displaystyle \sum_{k=0}^{n+1} {{n+1} \choose k}$
bluf | 15 de July de 2008 | 12:52

$latex 2^{n}=\left( 1+1\right) ^{n}=\overset{n}{\underset{k=0}{\sum}}1^{k}%
1^{n-k}\left(
\begin{array}
[c]{c}%
n\\
k
\end{array}
\right) =\overset{n}{\underset{k=0}{\sum}}\left(
\begin{array}
[c]{c}%
n\\
k
\end{array}
\right)$
¿Era esto, Vengoroso?
^DiAmOnD^ | 15 de July de 2008 | 16:26

Vaya tela, se me olvidaron las llaves y no vi la previa del post. Gracias Javier.
Gustavo | 15 de July de 2008 | 20:02

Yo soy el del problema.
Muchas gracias a Javier por el desarrollo tan detallado y a ^DiAmOnD^ por haberlo publicado.

Saludos.
Alex | 15 de July de 2008 | 21:15

Será mi navegador (iceweasel 3) o la página que me aparece en vez de la fórmula un mensaje que dice: Formula does not parse”, si antes no había ese problema.
Un saludo.
Juan Carlos | 15 de July de 2008 | 21:28

Alex se me ha adelantado, pero como veo que son “diferentes navegadores”, yo uso el FF3, me sumo al comentario. Me aparece en amarillo <>, aunque por breves momentos se muestra la fórmula y luego el mensaje anterior.
Saludos!!
Juan Carlos | 15 de July de 2008 | 21:32

Disculpen, lo que iba entre los simbolos “<>” es “Formula does not parse” y no le di vista previa, mis mas sinceras disculpas.
^DiAmOnD^ | 16 de July de 2008 | 02:55

No problem Juan Carlos, no pasa nada .

Pues no sé, es raro. Yo con firefox 2 no tengo ningún problema con ninguna de las fórmulas. ¿Alguien más tiene problemas? ¿Alguien sabe por qué puede ser?
Omar-P | 16 de July de 2008 | 03:03

Hace unas horas por aquí también aparecieron las frases en color amarillo en todo el post, en lugar de las fórmulas, pero ahora se arregló.
^DiAmOnD^ | 16 de July de 2008 | 03:07

Ah, pues igual era un error transitorio. A ver si no nos vuelve a suceder más.
Omar-P | 16 de July de 2008 | 04:16

Aquí hay un link sobre la frase de color amarillo.
http://www.en.forums.wordpress.com/topic.php?id=9339
vengoroso | 16 de July de 2008 | 10:45

bluf, eso era exactamente a lo que me refería; sencillo, directo, elegante

Hay otra manera, más geométrica, de definir los números combinatorios, que parte de la idea de trabajar con los puntos del plano con coordenadas naturales, y definir
$\left(\begin{array}{cc}n \\ k \end{array}\right)$ como el número de caminos “estrictamente crecientes” entre el origen y el punto $(k, n-k)$ , donde por “camino estrictamente creciente” nos referimos a un camino obtenido uniendo trozos de longitud 1 paralelos a los ejes y donde sólo permitimos movernos hacia arriba o hacia la derecha, y nunca volver atrás (esta definición de los coeficientes binomiales se puede encontrar en las notas de José Nieto Said Teoría Combinatoria)

El problema de hallar la suma de todos los binomiales se reduce entonces al de hallar todos los caminos de longitud $n$ . Como en cada paso tenemos dos opciones a seguir (hacia arriba o hacia la derecha), en total tendremos $2^n$ elecciones.

Sí, ya se que esta tampoco es por inducción…
Omar-P | 16 de July de 2008 | 10:56

vengoroso, gracias por la explicación y por el enlace.
Javier | 16 de July de 2008 | 11:34

Vengoroso, claro que es elegante, pero empleas un resultado que exige demostración, como es el desarrollo del Binomio de Newton, mientras que mi resultado se basa solo en la definicion de la suma, producto, factorial y numero combinatorio interno, es decir, no parto de una premisa que sabemos cierta todos aqui, pero que hay que demostrar.
vengoroso | 16 de July de 2008 | 17:13

Javier, hay una sutileza en lo que dices, que es la definición del coeficiente binomial.
Si tomas como definición del coeficiente binomial la fórmula aritmética (como haces tú) entonces sí es cierto que hay que demostrar la identidad del binomio de Newton. Lo que intentaba dar a entender es que hay muchas formas (todas equivalentes, por supuesto) de definir los coeficientes binomiales: la aritmética (que tú usas). la geométrica (la que pongo arriba), y justamente la “algebraica”, que viene a ser definir estos números como los coeficientes en la expansión de un binomio.

Si nos ponemos muy estrictos, la definición de “número combinatorio” clásica es como “la cantidad de combinaciones de $n$ elementos tomados de $k$ en $k$ ”, o bien como “La cantidad de subconjuntos de cardinal $k$ dentro de un conjunto con $n$ elementos”.

Si usáramos esta definición, sería necesario demostrar la identidad aritmética que tú usas. Por otro lado, con esta definición, el enunciado del problema se reduce a contar el total de subconjuntos de un conjunto con $n$ elementos, o lo que es lo mismo, la cardinalidad del conjunto de las partes, y usando (¡ahora sí!) inducción, se ve que $\# P(X) = 2^{\# X}$ .

Pero estoy divagando. Lo que quería señalar es que cuando tenemos varias definiciones equivalentes de la misma cosa a veces combiene pararse a elegir la más conveniente para el problema concreto que tengamos.
vengoroso | 16 de July de 2008 | 17:16

Avergüenzome de mí mismo, y me fustigo por la última línea del comentario anterior. Por “combiene” quería decir “conviene”.
Omar-P | 16 de July de 2008 | 19:30

Combiene y Combinatoria. Es notable como se ligaron los inicios de estas palabras. Pero no es vergüenza equivocarse y menos por una pequeñez. Saludos.
Luisito | 18 de July de 2008 | 22:41

Hay otra posibilidad que a mi me resulta mas elegante aun que la del binomio de Newton. Diria que se puede demostrar sin usar nada de aritmetica (?).

Que es el numero combinatorio $\left( \begin{matrix} n \\ k \end{matrix} \right)$ ? Sea la formula que fuere, es la manera de elegir k elementos dentro de un conjunto de n.

Que viene a ser entonces la expresion $\sum_{k=0}^n \left( \begin{matrix} n \\ k \end{matrix} \right)$ ? Es la manera de elegir 0, 1, 2, 3, o cualquier cantidad de elementos de un conjunto de n. Es decir que es la manera de elegir cualquier subconjunto de un conjunto de n elementos.

Cuantos subconjuntos tiene un conjunto de n elementos? Obviamente $2^n$ , ya que por cada elemento tenemos la opcion de elegirlo o no. De esta manera queda demostrada la igualdad usando solamente logica combinatoria, sin hacer ninguna cuenta, sin usar ningun teorema, y sin siquiera requerir saber calcular un numero combinatorio.

Alguna objecion? Les parece que esta demostracion no es suficientemente rigurosa?
Domingo H.A. | 10 de August de 2008 | 22:56

Aunque ya se ha hablado de esta curiosidad alguna que otra vez en el blog y ya muchos lo conocerán, les propongo demostrar que

$F_{n+1}=\displaystyle{\sum_{k=0}^{\lfloor \frac{n}{2}\rfloor}} {n-k \choose k}$

( $F_j$ ’s son los números de Fibonacci usuales)
Morgil | 16 de September de 2008 | 18:45

Interesante pagina, me ha salvado la vida. la resuesta en el post de javier es la resolucion por induccion de la primera formula del post??

Muchas gracias porq si me ha sacado de un apuro