Inducción sobre número combinatorio

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.

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

22 Comentarios

  1. \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}

    Publica una respuesta
  2. $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?

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

    Saludos.

    Publica una respuesta
  4. 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.

    Publica una respuesta
  5. 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!!

    Publica una respuesta
  6. Disculpen, lo que iba entre los simbolos “<>” es “Formula does not parse” y no le di vista previa, mis mas sinceras disculpas.

    Publica una respuesta
  7. 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?

    Publica una respuesta
  8. 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ó.

    Publica una respuesta
  9. 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… 😛

    Publica una respuesta
  10. 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.

    Publica una respuesta
  11. 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.

    Publica una respuesta
  12. Avergüenzome de mí mismo, y me fustigo por la última línea del comentario anterior. Por “combiene” quería decir “conviene”.

    Publica una respuesta
  13. 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.

    Publica una respuesta
  14. 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?

    Publica una respuesta
  15. 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)

    Publica una respuesta
  16. 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

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *