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}$ 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$
 A: 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?
A: 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.
A: 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}.
$$
A: $$\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}$$
