¿Cómo puedo probar que:
$$\sum\limits_{k=0}^m \binom{r}{k} \binom{m+n-r}{m-k} = \binom{m+n}{m} ~~~~~~~~~ (r <= m + n) $$
mediante el uso de una expresión algebraica de la identidad?
Mi Intento:
Sé de las funciones de generación: $$ (1 + x)^n = \sum\limits_{k=0}^n \binom{r}{k} x^k ~~~~~ y ~~~~~~ \frac {1}{(1 + x)^{n + 1}} = \sum\limits_{k=0}^{\infty} \binom{n + k}{k} x^k $$
y después de un poco de ensayo y error, se me ocurrió la identidad algebraica:
$$(1 - x)^r \frac {1}{(1 - x)^{n + r + 1}} = \frac {1}{(1 - x)^{n + 1}} ~~~~~~~~~~~~~~~~~ (a)$$
El lado derecho de (a) claramente coincide con la 2ª generación de la función. Así:
$$ \frac {1}{(1 + x)^{n + 1}} = \sum\limits_{m=0}^{\infty} \binom{n + m}{m} x^m $$
El lado izquierdo de (a) puede ser expresado como producto de sumas:
$$\begin{align*} \displaystyle{ (1 - x)^r \frac {1}{(1 - x)^{n + r + 1}} } &=\displaystyle{ \sum\limits_{m=0}^{\infty} \binom{r}{m} (-x)^m \sum\limits_{k=0}^{\infty} \binom{n + r + k}{k} x^k } \\ &=\displaystyle{ \sum\limits_{m=0}^{\infty} \sum\limits_{k=0}^{m} \binom{r}{k} (-x)^k \binom{n + r + m - k}{m - k} x^{m-k} } \\ &=\displaystyle{ \sum\limits_{m=0}^{\infty} \sum\limits_{k=0}^{m} \binom{r}{k} \binom{n + r + m - k}{m - k} (-1)^k x^m } \end{align*}$$
Pero ahora estoy atascado ya que no sé cómo hacer:
$$ \binom{n + r + m - k}{m - k} (-1)^k ~~~~ equal ~~~~ \binom{m+n-r}{m-k} ~~~~~ ????? $$
para completar la prueba.
Mi método de trabajo o debo usar otro algebraica de identidad? Soy bastante nuevo a la combinatoria así que por favor mantenga los conceptos comprensibles para un principiante. Gracias :)
EDITAR
La respuesta
Resulta que mi ecuación no se me toma en cualquier lugar cerca de la respuesta - LOL! Aquí está la respuesta con la nueva identidad algebraica:
$$\begin{align*} (1 + x)^r (1 + x)^{m+n-r} &= (1 + x)^{m + n} \\ \sum\limits_{m=0}^r \binom{r}{m} x^m \sum\limits_{k=0}^{m + n-r} \binom{n+m-r}{k} x^k &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \sum\limits_{m=0}^{r + (m+n-r)} \sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} x^m &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \sum\limits_{m=0}^{m+n} \sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} x^m &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \end{align*}$$
Igualando coeficientes se tiene:
$$\sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} = \binom{n+m}{m} ~~~~~~~~~~~~~~~~ QED!!! $$
