$\sum_{i=0}^m \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$ Prueba combinatoria

Question

¿Hay una prueba combinatoria simple para la identidad siguiente?

$$\sum_{0\leq i \leq m} \binom{m-i}{j}\binom{n+i}{k} =\binom{m + n + 1}{j+k+1}$$ where $m,j \geq 0$, $k \geq n \geq 0$.

Answer 1

Recuento $(j+k+1)$ elemento de subconjuntos de un conjunto ordenado ($m+n+1$) de los elementos, la organización de los subgrupos por el valor de la $(j+1)$-ésimo elemento más grande en el subconjunto. El producto de dos coeficientes binomiales en el lado izquierdo de la ecuación es el número de formas de elegir el resto del subconjunto cuando la $(j+1)$-ésimo más grande de los elementos del subconjunto es el $(m-i)$-ésimo elemento más grande en el conjunto.

Creo que esta fórmula se llama el doble de Vandermonde o negativo de Vandermonde de identidad.

Edit. La desigualdad entre los $n$ $k$ en la pregunta tiene la señal equivocada, debería ser $n \leq k$.

Answer 2

(Esencialmente el mismo que el anterior)
Contando el número de caminos de enrejado de longitud l + j + k + 1 $(0,0)$ $(j+k+1,l)$ % pasos $(0,1)$y $(1,0)$ de dos maneras, podemos obtener esta identidad. Cada ruta incluye $(j,s)$ $(j+1,s)$ paso $(s=0,1\ldots l)$. De esta manera, podemos dividir trazados en l + 1 grupos que son mutuamente excluyentes. Por lo tanto,
$\sum_{0\leq s \leq l} \binom{s+j}{j}\binom{l-s+k}{k} =\binom{l+j+k+1}{l}$
Ajuste del $l=m+n-(j+k)$, $s=(m-j-i)$, tenemos la identidad en cuestión.