Prove that $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$

A combinatorial proof is also possible. I have $m+n+1$ white balls numbered $0$ through $m+n$. I’m going to paint $m+2$ of them red, then choose any of the red balls except the one with the highest number and put a gold star on it, and I want to know how many different outcomes are possible.

Suppose that the highest-numbered red ball is ball $m+k$. There are $m+k$ balls with smaller numbers (since I started the numbering at $0$), so there are $\binom{m+k}m$ ways to choose the other $m$ red balls that don’t have the gold star. Once they’ve been chosen, there are $k$ ways to pick one of the remaining balls numbered below $m+k$, paint it red, and slap a gold star on it. Thus, there are $k\binom{m+k}m$ outcomes in which ball $m+k$ is the highest-numbered red ball. Summing over $k$ gives the total number of possible outcomes: it’s

$$\sum_{k=0}^nk\binom{m+k}m\;.$$

But we can count these outcomes in another way. There are $\binom{m+n+1}{m+1}$ ways to choose $m+1$ balls to be the unstarred red balls, and we can then choose any of the remaining $n$ balls to be the starred red ball, so there are

$$n\binom{m+n+1}{m+1}\tag{1}$$

ways to choose a set of $m+2$ balls, paint them red, and put a gold star on one of the balls. However, this includes the outcomes in which the gold star is on the highest-numbered red ball, and we don’t want those. For each possible set of $m+2$ red balls there is exactly one unwanted outcome, the one in which we put the gold star on the highest-numbered red ball, and there are

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

possible sets of red balls, so we need to subtract this from $(1)$ to get the correct count of

$$n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}\;.$$

This shows that

$$\sum_{k=0}^nk\binom{m+k}m=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}\;,$$

as desired.

Added: Let me suggest a way to proceed from the point at which you got stuck with your induction argument. First, it’s not too hard to notice that you have both $n\binom{m+n+1}{m+1}$ and $n\binom{m+n+1}m$, which can be combined using Pascal’s identity:

$$\begin{align*} &\sum_{k=0}^nk\binom{m+k}m+(n+1)\binom{m+n+1}m\\ &\qquad=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}+(n+1)\binom{m+n+1}m\\ &\qquad=n\left(\binom{m+n+1}{m+1}+\binom{m+n+1}m\right)+\binom{m+n+1}m-\binom{m+n+1}{m+2}\\ &\qquad=n\binom{m+n+2}{m+1}+\binom{m+n+1}m-\binom{m+n+1}{m+2}\;.\tag{1} \end{align*}$$

You want to show that this is equal to

$$(n+1)\binom{m+n+2}{m+1}-\binom{m+n+2}{m+2}\;.\tag{2}$$

You might try taking the difference and trying to show that it’s $0$. Subtracting $(1)$ from $(2)$, we get

$$\binom{m+n+2}{m+1}-\binom{m+n+2}{m+2}-\binom{m+n+1}m+\binom{m+n+1}{m+2}\;.\tag{3}$$

Pascal’s identity allows us to combine the second and fourth terms:

$$\binom{m+n+2}{m+2}=\binom{m+n+1}{m+2}+\binom{m+n+1}{m+1}\;,$$

so

$$\binom{m+n+1}{m+2}-\binom{m+n+2}{m+2}=-\binom{m+n+1}{m+1}\;,$$

and $(3)$ reduces to

$$\binom{m+n+2}{m+1}-\binom{m+n+1}{m+1}-\binom{m+n+1}m\;,$$

and one more application of Pascal’s identity verifies that this is indeed $0$.

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

Inductive Step. 1: $n\longrightarrow0$

$\sum_{k=0}^{n=0}k{m+k \choose m}=0$ and $n{m+n+1\choose m+1}-{m+n+1 \choose m+2}=0-0=0$.

the equation is satisfied.

Inductive Step. 2: $n\longrightarrow n$

$$\sum_{k=0}^nk{m+k \choose m}=$$ By Pascal's identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} \Rightarrow \binom{n}{k} - \binom{n-1}{k}= \binom{n-1}{k-1} \Rightarrow \binom{n+1}{k+1} - \binom{n-1+1}{k+1}= \binom{n-1+1}{k-1+1}= $ $\binom{n+1}{k+1} - \binom{n}{k+1}= \binom{n}{k}$ $$\sum_{k=0}^nk\left[\binom{m+k+1}{m+1}-\binom{m+k}{m+1}\right]=$$ $$\sum_{k=0}^nk\binom{m+k+1}{m+1}-\sum_{k=0}^nk\binom{m+k}{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n-1}(k+1)\binom{m+(k+1)}{m+1} + 0\binom{m+ 0 }{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n-1}(k+1)\binom{m+k+1}{m+1}=$$

$$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}(k-(k+1))\binom{m+k+1}{m+1}=$$ $$n\binom{m+n+1}{m+1}+\sum_{k=0}^{n-1}-1\binom{m+k+1}{m+1}=$$ By the Hockey-Stick identity:

$\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}$ $$n\binom{m+n+1}{m+1}-\binom{m+(n-1)+1 +1}{m+2}=$$ $$n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2}$$

The equation is satisfied.

Inductive Step. 3: $n\longrightarrow (n+1)$

$$\sum_{k=0}^{(n+1)}k{m+k \choose m}=$$

$$\sum_{k=0}^{(n+1)}k\left[\binom{m+k+1}{m+1}-\binom{m+k}{m+1}\right]=$$ $$\sum_{k=0}^{(n+1)}k\binom{m+k+1}{m+1}-\sum_{k=0}^{(n+1)}k\binom{m+k}{m+1}=$$ $$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n}(k+1)\binom{m+(k+1)}{m+1} + 0=$$

$$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}k\binom{m+k+1}{m+1}-\sum_{k=0}^{n}(k+1)\binom{m+k+1}{m+1}=$$

$$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}(k-(k+1))\binom{m+k+1}{m+1}=$$ $$(n+1)\binom{m+(n+1)+1}{m+1}+\sum_{k=0}^{n}-1\binom{m+k+1}{m+1}=$$

By the Hockey-Stick identity:

$\sum_{k=r}^n\binom{k}{r}=\binom{n+1}{r+1}$ $$(n+1)\binom{m+(n+1)+1}{m+1}-\binom{m+(n+1) +1}{m+2}$$

The equation is satisfied.

q.e.d

Here is a somewhat different approach. We use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ in a series. This way we can write e.g. \begin{align*} [x^k](1+x)^n=\binom{n}{k} \end{align*}

We obtain for $m,n\geq 0$ \begin{align*} \sum_{k=0}^n&k\binom{m+k}{m}\\ &=\sum_{k=1}^nk[x^m](1+x)^{m+k}\tag{1}\\ &=[x^m](1+x)^{m+1}\sum_{k=1}^nk(1+x)^{k-1}\tag{2}\\ &=[x^m](1+x)^{m+1}D_x\left(\sum_{k=1}^n(1+x)^k\right)\tag{3}\\ &=[x^m](1+x)^{m+1}D_x\left(\frac{1-(1+x)^{n+1}}{1-(1+x)}\right)\tag{4}\\ &=[x^m](1+x)^{m+1}\left[\frac{n(1+x)^n}{x}-\frac{(1+x)^n}{x^2}+\frac{1}{x^2}\right]\tag{5}\\ &=n[x^{m+1}](1+x)^{m+n+1}-[x^{m+2}](1+x)^{m+n+1}+[x^{m+2}](1+x)^{m+1}\tag{6}\\ &=n\binom{m+n+1}{m+1}-\binom{m+n+1}{m+2} \end{align*} and the claim follows

Comment:

• In (1) we apply the coefficient of operator.

• In (2) we do a little rearrangement by using the linearity of the coefficient of operator.

• In (3) we use the differential operator $D_x:=\frac{d}{dx}$.

• In (4) we use the formula for the finite geometric series.

• In (5) we differentiate the expression.

• In (6) collect terms and apply the formula \begin{align*} [x^{p+q}]A(x)=[x^p]x^{-q}A(x) \end{align*}

• In (7) we select the coefficients of $x^{m+1}$ and $x^{m+2}$. Note the coefficient of $x^{m+2}$ in the last term is zero, since the polynomial $(1+x)^{m+1}$ has degree less than $m+2$.