Htykuut

How can I prove for $m,nge0$:

$$sum_{i=0}^nsum_{j=0}^i{jchoose m}={n+2choose m+2}$$

I know you can start both sums from $m$ because every value below is zero but I am getting stuck trying to get algebraic proof.

A formula issued from Pascal Triangle:

$${ichoose j} = {i-1choose j-1}+{i-1choose j} = {i-1choose j-1}+{i-2choose j-1}+{i-2choose j} = ...$$

$${ichoose j} = sum_{k=j-1}^{i-1}{kchoose j-1}$$

Then the result is obtained by applying this formula twice:

$$sum_{i=0}^nsum_{j=0}^i{jchoose m}= sum_{i=0}^n{i+1choose m+1} = {n+2choose m+2}$$

There's also a nice combinatorial proof here. Given $n+2$ distinct apples in a line, how many ways can I choose $m+2$ of them? The right-hand side clearly counts this directly, so we focus our attention on the left-hand side.

Number the apples $1, 2, dots, n+2$. Our process of choosing $m+2$ apples is as follows:

1. Pick $0 leq i leq n$, and select apple $i+2$.


2. Pick $0 leq j leq i$, and select apple $j+1$
   


3. Pick $m$ apples among those ranging from $1$ to $j$.

This gives the summation on the left-hand-side; to see that it also counts exactly the ways to choose $m+2$ apples, note that this procedure simply picks the two apples with highest labels first, and then picks the other $m$.

Let $[x^m] f(x)$ denote the coefficient of $x^m$ in the expansion of $f(x)$.
$$
sum_{i=0}^nsum_{j=0}^i{jchoose m}=[x^m]sum_{i=0}^nsum_{j=0}^i{(x+1)^j}
= [x^m]sum_{i=0}^n{frac{(x+1)^{i+1}-1}{x}}= [x^{m+1}]sum_{i=0}^n(x+1)^{i+1}
= [x^{m+1}]frac{(x+1)^{n+2}-(x+1)}{x}=binom{n+2}{m+2}
$$
$blacksquare$