1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Ofya
    Dec 3, 2018 at 21:41
  • $\begingroup$ @Ofya It's typical to define $\binom{n}{m}$ to be $0$ when $m > n$. $\endgroup$ Dec 3, 2018 at 21:44
  • 1
    $\begingroup$ @Austin thanks, so it actually doesn't make a difference whether the lower bound of the sum is 0 or m $\endgroup$
    – Ofya
    Dec 3, 2018 at 21:45

3 Answers 3

6
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.