Prueba para este coeficiente binomial ' ecuación de s

Question

Para $k, l \in \mathbb N$ $$\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i=\binom{k+l+2}{k+1}-1$$ ¿Cómo puedo demostrarlo?

Pensé que algunas de las ideas con el triángulo de Pascal, contando con rutas de acceso en la red y simple deformación de la fórmula.

Se puede comprobar aquí (wolframalpha).

Si la prueba es difícil, por favor, hágamelo saber de la idea principal.

Lo siento por mi pobre inglés.

Gracias.

EDITAR: Tengo la gran y breve prueba de uso de Hockey stick de identidad por Anubhab Ghosal, sino porque de esta forma, también podría obtener la Robert Z especializada de respuesta. Pues no creo que se duplican.

Answer 1

<span class="math-container">$$\displaystyle\sum{i=0}^k\sum{j=0}^l\binom{i+j}i=\sum{i=0}^k\sum{j=i}^{i+l}\binom{j}i=\sum_{i=0}^k\binom{i+l+1}{i+1} \ ^{[1]}$$</span>

<span class="math-container">$$=\sum{i=0}^k\binom{i+l+1}{l}=\sum{i=l}^{k+l+1}\binom{i}{l}−1=\binom{k+l+2}{k+1}-1\ ^{[1]}$$</span>

1. palo de hockey identidad

Answer 2

Su idea acerca de una combinatoria de la prueba , la cual está relacionada a contar las rutas de acceso en una red es una buena!

El binomio $\binom{i+j}i$ los recuentos de las rutas en la red de la $(0,0)$ a $(i,j)$ sólo va a la derecha o hacia arriba. Así que el doble de la suma de la $$\sum_{i=0}^k\sum_{j=0}^l\binom{i+j}i-1$$ cuenta el número de todos los caminos de $(0,0)$ a cualquier vértice en el interior del rectángulo $(0,k)\times (0,l)$ diferente de $(0,0)$.

Ahora considere las rutas de la $(0,0)$ a $(k+1,l+1)$ diferentes de $$(0,0)\a (0,l+1)\a (k+1,l+1)\quad\text{y}\quad (0,0)\a (k+1,0)\a (k+1,l+1)$$ que son $$\binom{k+l+2}{k+1}-2.$$

Ahora cualquier ruta de acceso de la primera clase puede ser completado a una ruta de acceso de la segunda clase por el cambio de dirección, ir a la frontera del rectángulo $(0,k+1)\times(0,l+1)$ , para pasar luego a la esquina de la $(k+1,l+1)$ a lo largo del lado.

Es este un bijection entre el primer conjunto de caminos y la segunda?