Prove $\sum_{i=0}^n\sum_{j=0}^i{j\choose m}={n+2\choose m+2}$ How can I prove for $m,n\ge0$:
$$\sum_{i=0}^n\sum_{j=0}^i{j\choose m}={n+2\choose 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: A formula issued from Pascal Triangle:
$${i\choose j} = {i-1\choose j-1}+{i-1\choose j} = {i-1\choose j-1}+{i-2\choose j-1}+{i-2\choose j} = ...$$
$${i\choose j} = \sum_{k=j-1}^{i-1}{k\choose j-1}$$
Then the result is obtained by applying this formula twice:
$$\sum_{i=0}^n\sum_{j=0}^i{j\choose m}= \sum_{i=0}^n{i+1\choose m+1} = {n+2\choose m+2}$$
A: Let $[x^m] f(x)$ denote the coefficient of $x^m$ in the expansion of $f(x)$.
$$
\sum_{i=0}^n\sum_{j=0}^i{j\choose m}=[x^m]\sum_{i=0}^n\sum_{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$
A: 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:


*

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

*Pick $0 \leq j \leq i$, and select apple $j+1$

*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$.
