Prove that $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$ Can someone please see the work I have so far for the following proof and provide guidance on my inductive step?
Prove that if $m,n\in\mathbb{N}$, then $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$
Base Case. Let n=0. Then $\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$. Thus for $n=0$ our equation is satisfied.
Inductive Step. Let $n\ge0$. Assume $\sum_{k=0}^nk{m+k \choose m}=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}$. Now observe that
$$\begin{align*}\sum_{k=0}^{n+1}k{m+k \choose m}&=\\
\sum_{k=0}^{n}k{m+k \choose m}+(n+1){m+n+1\choose m}&=n{m+n+1\choose m+1}-{m+n+1 \choose m+2}+(n+1){m+n+1\choose m} \end{align*}$$
This is where I'm getting stuck... using Pascal's Identity to combine some of these terms seems ideal. However, the factors of $n$ and $n+1$ are making a clever manipulation difficult for me.
 A: 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$.
A: $$\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
A: 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$.
A: $\newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack}
 \newcommand{\dd}{\mathrm{d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,}
 \newcommand{\ic}{\mathrm{i}}
 \newcommand{\mc}[1]{\mathcal{#1}}
 \newcommand{\mrm}[1]{\mathrm{#1}}
 \newcommand{\pars}[1]{\left(\,{#1}\,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,}
 \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}k{m + k \choose m} =
n{m + n + 1 \choose m + 1} - {m + n + 1 \choose m + 2}:\ ?\,,\qquad
m, n \geq 0}$.



*

*Our first step is 'to move' the index $\ds{k}$ to the binomial lower argument as follows:
\begin{align}
\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & =
\sum_{k = 0}^{n}k{m + k \choose k} =
\sum_{k = 0}^{n}k{-m - k + k - 1 \choose k}\pars{-1}^{k}
\\[5mm] & =
\sum_{k = 0}^{n}\pars{-1}^{k}\,k{-m - 1 \choose -m - 1 - k}\label{1}\tag{1}
\end{align}

*Hereafter, we'll use the identity 
\begin{equation}
{p \choose q} = \oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{p} \over z^{q + 1}}
\,{\dd z \over 2\pi\ic}\label{2}\tag{2}
\end{equation}
With \eqref{1} and \eqref{2}:
\begin{align}
\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & =
\sum_{k = 0}^{n}\pars{-1}^{k}\,k\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{-m - 1} \over z^{\pars{-m - 1 - k} + 1}}
\,{\dd z \over 2\pi\ic}
\\[5mm] & =
\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 1} \over z^{-m}}
\sum_{k = 0}^{n}k\,\pars{-z}^{k}\,{\dd z \over 2\pi\ic}
\\[1cm] & =
\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 1} \over z^{-m}}\,\times
\\[5mm] &
\bracks{\pars{-1}^{n}n\, {z^{n + 2} \over \pars{1 + z}^{2}} + \pars{-1}^{n}\pars{n + 1}\,{z^{n + 1} \over \pars{1 + z}^{2}} -
{z \over \pars{1 + z}^{2}}}\,{\dd z \over 2\pi\ic}\label{3}\tag{3}
\end{align}
In \eqref{3}, the $\ds{\bracks{\cdots}}$-bracket expression is the result of
$\ds{\sum_{k = 0}^{n}k\,\pars{-z}^{k}}$.

*\eqref{3} is reduced to


\begin{align}
&\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}}
\\[5mm] = &\
\pars{-1}^{n}\,n\oint_{\verts{z}\ =\ 1^{-}}
{\pars{1 + z}^{-m - 3} \over z^{-m - n - 2}}
\,{\dd z \over 2\pi\ic} +
\pars{-1}^{n}\pars{n + 1}
\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 3} \over z^{-m - n - 1}}
\,{\dd z \over 2\pi\ic}
\\[5mm] &\ -
\oint_{\verts{z}\ =\ 1^{-}}{\pars{1 + z}^{-m - 3} \over z^{-m - 1}}
\,{\dd z \over 2\pi\ic}
\end{align}
With the identity \eqref{2}, the last expression becomes
\begin{align}
\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & =
\pars{-1}^{n}\,n{-m - 3 \choose -m - n - 3} +
\pars{-1}^{n}\pars{n + 1}{-m - 3 \choose -m - n - 2} - {-m - 3 \choose -m - 2}
\label{4}\tag{4}
\end{align}
In this expression, the binomial arguments are negative since $\ds{m, n \geq 0}$. Therefore, it's convenient to use the following identity:
\begin{equation}
{p \choose q} = \pars{-1}^{p - q}{-q - 1 \choose p - q}\,,\qquad q \leq p
\end{equation}
 4. \eqref{4} is reduced to:
\begin{align}
\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} & =
\pars{-1}^{n}\,n\,\pars{-1}^{n}{m + n + 2 \choose n} +
\pars{-1}^{n}\pars{n + 1}\,\pars{-1}^{n - 1}{m + n + 1 \choose n - 1}
\\ &
-\,\pars{-1}^{-1}\ \overbrace{{m + 1 \choose -1}}^{\ds{=\ 0}}
\\[1cm] & =
n{m + n + 2 \choose m + 2} - \pars{n + 1}{m + n + 1 \choose m + 2}
\\[5mm] & =
n\ \overbrace{\bracks{{m + n + 1 \choose m + 2} + {m + n + 1 \choose m + 1}}}
^{\ds{\mbox{Pascal Triangule Identity}}}\ -\
\pars{n + 1}{m + n + 1 \choose m + 2}
\end{align}
The last expression leads to
$$
\color{#f00}{\sum_{k = 0}^{n}k{m + k \choose m}} 
=
\color{#f00}{n{m + n + 1 \choose m + 1} - {m + n + 1 \choose m + 2}}
$$
