Suma de combinaciones

Question

Posible duplicado:
prueba del teorema del binomio simple

¿Por qué es $${6\choose 0} + {7\choose 1} + \ldots + {n+6 \choose n} = {n+7 \choose n}\;?$$

Answer 1

CONSEJOS: El argumento algebraico es una prueba por inducción: verificar la igualdad para $n=0$ y demostrar que si $${6\choose 0} + {7\choose 1} + \ldots + {n+6 \choose n} = {n+7 \choose n}\;,$$ entonces $${6\choose 0} + {7\choose 1} + \ldots + {(n+1)+6 \choose {n+1}} = {(n+1)+7 \choose {n+1}}\;.$$ Esta es una aplicación bastante directa de la identidad del triángulo de Pascal.

Para el argumento combinatorio, observe que $\binom{n+7}n=\binom{n+7}7$ es el número de formas de elegir un $7$ -subconjunto de elementos de $\{1,2,\dots,n+7\}$ y $\binom{k+6}k=\binom{k+6}6$ es el número de formas de elegir un $7$ -subconjunto de elementos de $\{1,\dots,n+7\}$ cuyo mayor elemento es el número $k+1$ . Es decir, elegir un $7$ -cuyo elemento mayor es $10$ , primero se elige $10$ y luego tienes que elegir $6$ de los números $\{1,\dots,9\}$ .

Answer 2

La fórmula recursiva estándar para los coeficientes binomiales es

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

Existe una técnica para la recursión llamada "desenrollar", en la que se sustituye repetidamente una recursión en su ecuación por sí misma. Aquí si invertimos los términos y luego sustituimos repetidamente obtenemos:

$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$

$\binom{n}{k} = \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-2}{k-2}$

$\vdots$

$\binom{n}{k} = \binom{n-1}{k} + \binom{n-2}{k-1} + \binom{n-3}{k-2} + \cdots + \binom{n-k}{0}$