Prueba combinatoria de la identidad $\sum_{k=0}^n\binom{x+k}{k}=\binom{x+n+1}{n}$?

Question

Possible Duplicate:
Demostración combinatoria de dos identidades

La identidad $$ \sum_{k=0}^n\binom{x+k}{k}=\binom{x+n+1}{n} $$ puede ser verificada mediante una inducción directa, pero ¿existe algún argumento combinatorio agradable que lo demuestre? Aquí $x$ es un entero no negativo, por cierto.

Siempre he encontrado que los argumentos combinatorios facilitan recordar tales identidades y entenderlas intuitivamente, por lo que agradecería ver uno. Gracias.

Answer 1

Reescríbelo como $$\sum_{k=0}^n\binom{x+k}x=\binom{x+n+1}{x+1}\;.$$ El lado derecho claramente cuenta los subconjuntos de $[x+n+1]$ de tamaño $x+1$. El lado izquierdo descompone ese conteo según el elemento más grande del subconjunto. Es decir, si el elemento más grande es $x+k+1$, los otros $x$ elementos deben ser elegidos del conjunto $[x+k]$, y esto se puede hacer de $\binom{x+k}x$ formas. (Aquí uso $[n]$ para $\{1,\dots,n\}$.)