Binomial coefficients identity : $\sum_{k=1}^{n-m+1} k\binom{n-k+1}{m}=\binom{n+2}{m+2}$

Question

For any positive integer m&n.$n\ge m$ , let $\left( {\begin{array}{*{20}{c}} n\\ m \end{array}} \right) = {}^n{C_m}$. Prove that $\left( {\begin{array}{*{20}{c}} n\\ m \end{array}} \right) + 2\left( {\begin{array}{*{20}{c}} {n - 1}\\ m \end{array}} \right) + 3\left( {\begin{array}{*{20}{c}} {n - 2}\\ m \end{array}} \right) + .. + \left( {n - m + 1} \right)\left( {\begin{array}{*{20}{c}} m\\ m \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {n + 2}\\ {m + 2} \end{array}} \right)$

My approach is as follow $n=4, m=2$

$\left( {\begin{array}{*{20}{c}} 4\\ 2 \end{array}} \right) + 2\left( {\begin{array}{*{20}{c}} 3\\ 2 \end{array}} \right) + 3\left( {\begin{array}{*{20}{c}} 2\\ 2 \end{array}} \right) = \left( {\begin{array}{*{20}{c}} 6\\ 4 \end{array}} \right) = 15$

$6 + 6 + 3 = 15 \Rightarrow LHS = RHS$

But not able to solve it via property

Answer 1

Starting from

$$\sum_{k=1}^{n-m+1} k {n-k+1\choose m}$$

we re-write as

$$\sum_{k=1}^{n-m+1} k {n-k+1\choose n-m+1-k} = [z^{n-m+1}] (1+z)^{n+1} \sum_{k=1}^{n-m+1} k \frac{z^k}{(1+z)^k}$$

Here the coefficient extractor enforces the upper limit of the sum and we obtain

$$[z^{n-m+1}] (1+z)^{n+1} \sum_{k\ge 1} k \frac{z^k}{(1+z)^k} \\ = [z^{n-m+1}] (1+z)^{n+1} \frac{z/(1+z)}{(1-z/(1+z))^2} = [z^{n-m+1}] (1+z)^{n+1} z (1+z) \\ = [z^{n-m}] (1+z)^{n+2} = {n+2\choose n-m} = {n+2\choose m+2}$$

as claimed.

Answer 2

Here is a combinatorial approach. Consider the set $$\{ 1,2,3,4,\ldots,n-1,n,n+1,n+2\}$$

We will pick $m+2$ distinct numbers. This can be done randomly in $\binom{n+2}{m+2}$ ways.

Another way to do the same would be prioritizing the second smallest element.

If second smallest number is $2$, we can choose $1$ as the smallest element and select $m$ out of remaining $n$ numbers. $\binom{n}{m}$ ways.

If second smallest number is $3$, we can choose the smallest in two ways out of $1,2$ and select $m$ out of remaining $n-1$ in $\binom{n-1}{m}$ ways.

In general, if second smallest choice is $i+1$, the smallest can be picked in $i$ ways and rest in $\binom{(n+2)-(i+1)}{m}=\binom{n-i+1}{m}$ ways.

Summing over all valid values of $i$, LHS=RHS is proved.