Can anyone give a combinatorial proof of the identity ${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+...+(n-m+1){m \choose m}={n+2 \choose m+2}$

Question

Can anyone give a combinatorial proof of the identity

$${n \choose m} + 2{n-1 \choose m}+3{n-2 \choose m}+\ldots+(n+1-m){m \choose m}={n+2 \choose m+2}$$

I am finding difficult as $n$ is varying instead of $m$

Answer 1

Let $S$ be the set of all binary strings of length $n+2$ that have exactly $m+2$ $1$'s.

We want to count the number of elements in $S$ in two different ways. On the one hand, we know that $|S|=\binom{n+2}{m+2}$.

Now, fix $1\leq i\leq n+1-m$. Let $S_{i}$ be the subset of $S$, whose strings have a $1$ in the $(i+1)$'st entry and exactly one $1$ among the first $i$ entries. Clearly there are $i$ ways to place a $1$ among the first $i$ entries of the string. Since the $(i+1)$'st entry must be a $1$, the remaining $m$ $1$'s will be among the last $(n+2)-(i+1)=n+1-i$ entries. There are $\binom{n+1-i}{m}$ ways to place these remaining $1$'s. Thus, there are $|S_{i}|=i\cdot\binom{n+1-i}{m}$.

Now, note that $S=\underset{1\leq i\leq n+1-m}{\bigcup}S_{i}$. Furthermore, the $S_{i}$'s are all disjoint. ${\bf\it Why?}$

Therefore, $$ \binom{n+2}{m+2}=|S|=\underset{1\leq i\leq n+1-m}{\sum}|S_{i}|=\underset{1\leq i\leq n+1-m}{\sum}i\cdot\binom{n+1-i}{m}. $$

Answer 2

HINT: You want to count the subsets of $\{0,1,\ldots,n+1\}$ that have $m+2$ elements. Clearly there are $\binom{n+2}{m+2}$ of them. However, we can also count them in batches according to the second-smallest number in the set.

How many $(m+2)$-element subsets of $\{0,1,\ldots,n+1\}$ have $k$ as their second-smallest element?

Answer 3

One way is by induction. If $n = m$, then we have

$$ \binom{n}{m} = \binom{n+2}{m+2} $$

which is true, as both sides equal $1$. Next, suppose that

$$ \binom{m+k}{m} + 2\binom{m+k-1}{m} + 3\binom{m+k-2}{m} + \cdots + (k+1)\binom{m}{m} = \binom{m+k+2}{m+2} $$

for some $k \geq 0$. Then, for $k+1$, your left-hand side equals

\begin{align} L & = \binom{m+k+1}{m} + 2\binom{m+k}{m} + 3\binom{m+k-1}{m} + \cdots + (k+2)\binom{m}{m} \\ & = \binom{m+k+1}{m} + \binom{m+k}{m} + \binom{m+k-1}{m} + \cdots + \binom{m}{m} + \binom{m+k+2}{m+2} \\ & = \binom{m+k+2}{m+1} + \binom{m+k+2}{m+2} \qquad \leftarrow \text{hockey-stick identity} \\ & = \binom{m+k+3}{m+2} \end{align}

which establishes the proposition.

Answer 4

$$\begin{align} \sum_{r=1}^{n-m+1}r\binom {n-r+1}m &=\sum_{k=m}^n(n-k+1)\binom km &&\text{putting }k=n-r+1\\ &=\sum_{k=m}^n\sum_{j=k}^n\binom km\\ &=\sum_{j=m}^n\sum_{k=m}^j\binom km\\ &=\sum_{j=m}^n\binom {j+1}{m+1}\\ &=\binom {n+2}{m+2}\qquad\blacksquare\end{align}$$