Argumento combinatorio para $\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$

Question

Necesito demostrar que $$\sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i} = \binom{n}{i}2^{n-i}$$

Sé que $\displaystyle \binom{n}{k}\binom{k}{i}$ es contar el número de formas de elegir $k$ elementos de $n$ y luego $i$ elementos de los $k$ Así que $\displaystyle \sum\limits_{k=i}^{n}\binom{n}{k}\binom{k}{i}$ es contar el número de formas de hacerlo $\forall k$ .

Sé que $\displaystyle \binom{n}{i} = \binom{n}{n-i}$ y que $2^{n-i}$ es el número de elementos del conjunto de potencia para $[n]\setminus[i]$ .

¿Cómo puedo demostrar que ambos lados son equivalentes? Estoy perplejo en este caso. ¿Alguien podría darme una indicación en la dirección correcta?

Answer 1

SUGERENCIA: En ambos lados se está dividiendo el conjunto de $n$ cosas en tres conjuntos. Uno de esos conjuntos contiene exactamente $i$ objetos, uno contiene $k-i$ para algunos $k$ y el tercero contiene el $n-k$ que quedan. Para el lado derecho, ten en cuenta que una vez que has elegido dos de esos conjuntos, ya no tienes que elegir el tercero: es simplemente lo que queda.

(Esta es una pista más escasa de lo que suelo dar, porque ya has hecho la mayor parte del trabajo: sólo tienes que ver cómo unir las piezas).

Answer 2

• Empecemos por el RHS: usted elige $i$ elementos entre $n$ (hay $\binom{n}{i}$ opciones), y luego elegir un subconjunto arbitrario de las restantes $n-i$ elementos ( $2^{n-i}$ opciones).

• Ahora, el LHS: se elige un tamaño de subconjunto $k\geq i$ y, a continuación, elija $k$ elementos fuera de $n$ y, a continuación, elija $i$ elementos fuera de este $k$ -conjunto de elementos $S$ . Al final, tienes un subconjunto de $i$ y un subconjunto arbitrario de $n-i$ (la unión de los elementos $k-i$ los elementos restantes de $S$ y del $n-k$ elementos).

Answer 3

Jugaremos un partido. Estamos con $n$ gente, pero no todos jugarán. Ahora elegiremos un equipo rojo (con $i$ miembros) y un equipo azul (no son equipos iguales: el número de miembros del equipo azul no es fijo). Hay ${n\choose i}$ maneras de elegir el equipo rojo - luego decidimos para cada persona que queda, si estará o no en el equipo azul (que son $2^{n-i}$ posibilidades) por lo que el total $${n\choose i}2^{n-i}$$ posibilidades.

---

También podemos elegir primero $k$ personas que jugarán (al menos $i$ ya que tendremos que ser capaces de hacer el equipo rojo. ${n\choose k}$ posibilidades). Después de eso, elegimos $i$ personas para estar en el equipo rojo ( ${k\choose i}$ posibilidades), lo que hace que el total de posibilidades $$\sum_{k=i}^n{n\choose k}{k\choose i}$$

Así, llegamos a la conclusión de que $$\sum_{k=i}^n{n\choose k}{k\choose i}={n\choose i}2^{n-i}$$