# Prove $\sum_{i=0}^n\sum_{j=0}^i{j\choose m}={n+2\choose m+2}$ [closed]

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.

• I'm not sure if i got the question right. Is m a number set beforehand? If so, for cases when m > 0, I'm not quite sure whether $0 \choose 1$ is defined or in general $n \choose m$ for m greater than n is defined. Shouldn't the lower bound of the sum be m?
– Ofya
Dec 3, 2018 at 21:41
• @Ofya It's typical to define $\binom{n}{m}$ to be $0$ when $m > n$. Dec 3, 2018 at 21:44
• @Austin thanks, so it actually doesn't make a difference whether the lower bound of the sum is 0 or m
– Ofya
Dec 3, 2018 at 21:45

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}$$

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}^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$$