Prueba $\sum\limits_{l=0}^m\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}=\binom{n+m}{m}$

Question

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

Mi solución: Traté de usar la identidad de Vandermonde: \begin{align} \sum_{l=0}^m\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}&=\sum_{l=0}^m\binom{k+l}{l}\binom{n-k-1+m-l}{m-l}\\ &=\binom{n+m-1}{m} \end{align}

¿En qué me equivoco? ¿Cómo demostrarlo de forma correcta?

Answer 1

La identidad de Vandermonde dice $$ \sum_{\color{blue}k = 0}^r \binom{m}{\color{blue}k}\binom{n}{r-\color{blue}k} = \binom{m + n}{r}. $$ Tenga en cuenta dónde se encuentra el $k$ aparece en la suma (sólo en la parte inferior). En su suma, hace el índice de suma, $l$ ¿aparecen sólo en la parte inferior?

Se puede demostrar esta identidad considerando las trayectorias de la red. Sea $\mathscr{L}(a,b)$ sea el conjunto de trayectorias de la red Norte/Este desde $(0,0)$ a $(a,b)$ . Entonces

$$ \mathscr{L}(n,m) \leftrightarrow \biguplus_{l = 0}^m \mathscr{L}(k,l) \times \mathscr{L}(n - (k + 1), m - l). \tag{1} $$ La descomposición se muestra a continuación.

Desde $|\mathscr{L}(a,b)| = \binom{a + b}{a} = \binom{a + b}{b}$ la descomposición $(1)$ da

$$ \binom{m + n}{m} = \sum_{l = 0}^m \binom{k + l}{k} \binom{n - k - 1 + m - l}{n - k - 1}. $$

Answer 2

El problema es que para usar Vandermonde, necesitas tener números fijos en la parte ascendente de los binomios. Usted tiene, en cambio $$\binom{k+\color{red}{l}}{l}\binom{n-k-1+m-\color{red}{l}}{m-l}.$$

Optaré por un argumento combinatorio:

Recordemos que $$\binom{n+m}{n}=|A|=|\{x\in \{0,1\}^{n+m}:|x|_1=n\}|,$$ donde $|x|_1=$ # de 1's en la cadena.

Consideremos ahora los conjuntos $$A_l = \{x\in A:\sum _{i=1}^{k+l} x_i =k \wedge x_{k+l+1}=1 \}.$$ entonces $A=\bigcup _{l=0}^n A_l$ y $A_l\bigcap A_j=\emptyset$ si $l\neq j.$ Así que $$\binom{n+m}{n}=|A|=|\bigcup _{l=0}^n A_l|=\sum _{l = 0}^n|A_l|,$$ pero para $A_l$ tiene que elegir el $k$ los en $k+l$ y $n-k-1$ en $n+m-(l+k+)$ así que $$|A_l|=\binom{l+k}{k}\binom{n+m-(l+k+1)}{n-k-1}.$$ Así que tu identidad sigue.

Answer 3

Podemos utilizar una generalización de la Identidad Vandermonde .

W \begin{align*} \color{blue}{\sum_{l=0}^m}&\color{blue}{\binom{k+l}{k}\binom{n-k-1+m-l}{n-k-1}}\\ &=\sum_{l=0}^m\binom{k+l}{l}\binom{n-k-1+m-l}{m-l}\tag{1}\\ &=(-1)^m\sum_{l=0}^m\binom{-k-1}{l}\binom{-n+k}{m-l}\tag{2}\\ &=(-1)^m\binom{-n-1}{m}\tag{3}\\ &\color{blue}{=\binom{n+m}{m}}\tag{4}\\ \end{align*} y se cumple la afirmación.

Comentario:

• En (1) aplicamos la identidad binómica $\binom{p}{q}=\binom{p}{p-q}$ dos veces.

• En (2) aplicamos la identidad binómica $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ dos veces.

• En (3) aplicamos la _Identidad Chu-Vandermonde_ .

• En (4) aplicamos de nuevo la identidad binómica $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ .