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.

Author: ^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 Comments

  1. ¿Por qué por inducción? Con lo bonito que es el binomio de Newton…

    Post a Reply
  2. \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}

    Post a Reply
  3. $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?

    Post a Reply
  4. Vaya tela, se me olvidaron las llaves y no vi la previa del post. Gracias Javier.

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

    Saludos.

    Post a Reply
  6. 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.

    Post a Reply
  7. 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!!

    Post a Reply
  8. Disculpen, lo que iba entre los simbolos «<>» es «Formula does not parse» y no le di vista previa, mis mas sinceras disculpas.

    Post a Reply
  9. 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?

    Post a Reply
  10. 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ó.

    Post a Reply
  11. Ah, pues igual era un error transitorio. A ver si no nos vuelve a suceder más.

    Post a Reply
  12. 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… 😛

    Post a Reply
  13. 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.

    Post a Reply
  14. 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.

    Post a Reply
  15. Avergüenzome de mí mismo, y me fustigo por la última línea del comentario anterior. Por «combiene» quería decir «conviene».

    Post a Reply
  16. 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.

    Post a Reply
  17. 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?

    Post a Reply
  18. 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)

    Post a Reply
  19. 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

    Post a Reply

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.

Submit a Comment

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

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.