# Proving $\binom{n}{m}+2\binom{n-1}{m}+…+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2}$

For $m,n\in\mathbb{N},\;n\geq m$, prove the following:

$$\tag{i}\binom{n}{m}+\binom{n-1}{m}+\binom{n-2}{m}+......+\binom{m}{m} = \binom{n+1}{m+1}$$ $$\tag{ii}\binom{n}{m}+2\binom{n-1}{m}+3\binom{n-2}{m}+......+(n-m+1)\binom{m}{m} = \binom{n+2}{m+2}$$

My Attempt:

For $(\mathrm{i})$, We can write $\binom{n}{m}$ as the coefficient of $x^m$ in $(1+x)^n$. Thus we can also write $\binom{n-1}{m}$ as the coefficient of $x^m$ in $(1+x)^{n-1}$ and $\binom{n-2}{m}$ as the coefficient of $x^m$ in $(1+x)^{n-2}$. So we have to find the coefficient of $x^m$ in

$$(1+x)^n+(1+x)^{n-1}+(1+x)^{n-2}+........+(1+x)^{m}$$

Using the formula for the sum of a geometric progression, this sum equals

$$\frac{(1+x)^{n+1}-(1+x)^m}{x}$$

So we now need to find the coefficient of $x^m$ in

$$\frac{(1+x)^{n+1}-(1+x)^m}{x}$$

or, equivalently, we need to find the coefficient of $x^{m+1}$ in $$(1+x)^{n+1}-(1+x)^m = \binom{n+1}{m+1}$$

We can use a similar method to solve $(\mathrm{ii})$. Can these questions be solved using combinatorial methods instead?

First problem: We have $n+1$ different doughnuts (labelled $1$ to $n+1$) lined up in a row, and want to choose $m+1$ of them for breakfast. This can be done in $\binom{n+1}{m+1}$ ways. Let us count another way.

Maybe the leftmost doughnut chosen is $1$. There are $\binom{n}{m}$ ways to choose the rest.

Maybe the leftmost doughnut chosen is $2$. There are then $\binom{n-1}{m}$ ways to choose the others.

And so on.

Second Problem: This is done similarly. This time we are choosing $m+2$ doughnuts from $n+2$ doughnuts, labelled $1$ to $n+2$ and lined up in that order.

Look at the leftmost two doughnuts chosen. If the second one is Doughnut $2$, there are $\binom{n}{m}$ ways to choose the rest.

If the second one chosen is Doughnut $3$, there are $2$ ways to choose the first one, and $\binom{n-1}{m}$ ways to choose the rest, for a total of $2\binom{n-1}{2}$.

If the second one chosen is Doughnut $4$, there are $3$ ways to choose the first one, and $\binom{n-2}{m}$ ways to choose the rest, for a total of $3\binom{n-2}{m}$.

And so on.

• You've missed one "$" sign. – user142971 Aug 21 '15 at 5:01 • @user36790: Thanks, fixed. – André Nicolas Aug 21 '15 at 5:08 Suppose$n \geq m$and there is a set$S$of$n + 2$objects, denoted as$o_1, o_2, \cdots, o_{n+2}$. Your task to sample$m + 2$objects from$S$. Let$X_i$denote the # of ways to choose$m + 2$objects such that the object with second minimum id is$o_i$. Easy to see that $$X_i = (i-1) \cdot { n + 2 - i \choose m }$$ So we have $$\sum_{i=2}^{n+2-m} X_i = {n \choose m} + 2\cdot{n-1 \choose m} + \cdots + (n + 1 -m) \cdot {m \choose m} = {n + 2 \choose m + 2}$$ Similar derivation can be applied to (i) with some minor modification. Instead of enumerating the second minimum id, you need to enumerate the minimum id instead. Maybe a bit late now but here is my answer: Consider counting the number of possible bit-strings of length$n+i$: $$\underbrace{111...\overbrace{\textbf{1}}^{i^{\text{th}}\ 1}...111}_{m+i\ 1\text{s}}\ 000...000$$ So, here$n$is the number of digits to the right of the$i^\text{th}\ 1$. The number of bit strings is given simply by$\binom{n+i}{m+i}$where$m$is the number of$1$s to the right of the$i^{\text{th}}\ 1$. We may also count bit strings for each possible position of the$i^{\text{th}}\ 1$(i.e. position$i$, position$i+1$up to position$i+n-m$) and sum these to give the same result. When the$i^{\text{th}}\ 1$is in a position$i+r$there are$i+r-1$digits to the left including$i-11$s and$n-r$digits to the right including$m1$s. So if we sum over$r$: $$\dbinom{n+i}{m+i} = \sum_{r=0}^{n-m} \dbinom{i+r-1}{i-1}\dbinom{n-r}{m}$$ Your two examples are special cases of this identity. If we put$i=1$and$i=2\$ we have the two required results:
$$\dbinom{n+1}{m+1} = \sum_{r=0}^{n-m} \dbinom{r}{0}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \dbinom{n-r}{m} = \dbinom{n}{m} + \dbinom{n-1}{m} + ... + \dbinom{m}{m}$$ and
$$\dbinom{n+2}{m+2} = \sum_{r=0}^{n-m} \dbinom{r+1}{1}\dbinom{n-r}{m} = \sum_{r=0}^{n-m} \left(r+1\right)\dbinom{n-r}{m} = 1\dbinom{n}{m} + 2\dbinom{n-1}{m} + ... + \left(n-m+1\right)\dbinom{m}{m}$$