Ejercicio de aplicación del teorema del binomio

Question

En mis apuntes de clase de matemáticas teóricas, se deja abierto el siguiente problema como ejercicio. El profesor cree que la solución debería ser fácil de ver, pero después de muchas horas, no puedo obtener la visión adecuada.

La siguiente identidad se puede demostrar utilizando el teorema del binomio.

$$\sum_{m = k}^{n}{{m \choose k}{n \choose m}} = {n \choose k}2^{n - k}$$

Answer 1

No tengo ni idea de cómo demostrarlo usando el teorema del binomio. Pero en realidad sólo hay una buena manera de demostrar que las cosas son iguales en combinatoria, y es formular la misma pregunta de dos maneras diferentes.

Para este, pensé en elegir un equipo de fútbol. Digamos que se les permite traer a toda la gente que quieran de $n$ solicitantes, pero sólo $k$ pueden ser los iniciadores.

Una forma de encontrar el número de formas de hacerlo sería eligiendo a todo el equipo, y luego eligiendo a los titulares de ese equipo. Podemos hacerlo contando los posibles equipos con $i$ jugadores donde $n \geq i \geq m$ . Para ello, debe elegir $i$ miembros de su $n$ y luego $k$ los titulares de la $i$ miembros del equipo. Luego se suman todos los posibles $i$ y tienes el lado izquierdo de la ecuación.

También podríamos elegir primero los titulares y añadir otros más tarde. El número de formas de elegir los entrantes sería entonces $n \choose k$ y luego podríamos añadir cualquier subconjunto de los restantes $n-k$ jugadores. Dado que hay $2^{n-k}$ tales subconjuntos, tenemos el lado derecho de su ecuación.

Tal vez seas mejor que yo en la manipulación de símbolos y puedas hacer alguna sustitución ingeniosa para demostrar esto usando el teorema del binomio, pero me gusta más este tipo de demostración.

Answer 2

¡Estoy de acuerdo con genisage en que la prueba de conteo es mejor aquí! Pero si realmente buscas la prueba del teorema del binomio, aquí tienes un método. Considere $(1 + 1 + x)^n$ . ¿Cuál es el coeficiente de la $x^k$ ?

Bueno, si miramos esto como $(2 + x)^n$ el teorema del binomio dice que el $k$ El término es ${n \choose k} 2^{n - k} x^k$ y, por lo tanto, el coeficiente del $x^k$ es ${n \choose k} 2^{n - k}$ .

Por otro lado, podríamos ver esto como $(1 + (1 + x))^n$ . El $m$ El término de esto se parece a ${n \choose m} 1^{n - m} (1 + x)^m = {n \choose m} (1 + x)^m$ . Oh, pero ahora tenemos que ampliar $(1 + x)^m$ y vemos el $k$ plazo (del $m$ de la legislatura), incluyendo el ${n \choose m}$ es $$ {n \choose m}{m \choose k} 1^{m - k} x^k = {n \choose m}{m \choose k} x^k. $$ Para obtener el coeficiente del $x^k$ necesitamos sumar todas las posibles $x^k$ términos de cada elección de $m$ . Por lo tanto, el coeficiente del $x^k$ El término es $\sum_{m = k}^n {n \choose m}{m \choose k}$ .