Demostrando que $\sum_{i = 0}^{m}{\binom{k+i}{k} \binom{n-i}{n-m}} = \binom{n+k+1}{m}$

Question

Objetivo: demostrar que $\displaystyle\sum_{i = 0}^{m}{\binom{k+i}{k} \binom{n-i}{n-m}} = \binom{n+k+1}{m}$

¿Cómo dar un argumento combinatorio, es decir, contar de dos maneras, para este problema? Lo he intentado eligiendo el elemento menor o mayor del conjunto, pero es difícil deshacerse del producto de dos binomios en el lado izquierdo. Cualquier idea se agradecería.

Answer 1

Si reescribimos la identidad como $$\sum_{i = 0}^{m}{\binom{k+i}{k} \binom{n-i}{n-m}} =\binom{n+k+1}{n+k+1-m}$$ entonces se puede demostrar considerando el valor de la $(k+1)$ -elemento en el (sub)conjunto de $n+k+1-m$ (que sólo pueden aceptar valores de $k+1$ à $k+m+1$ ).