TITLE: Prove $\sum_{i=0}^n\sum_{j=0}^i{j\choose m}={n+2\choose m+2}$
QUESTION [1 upvotes]: 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.

REPLY [2 votes]: 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$.
{"set_name": "stack_exchange", "score": 1, "question_id": 3024648}