<s>[INST] 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.
 [/INST] 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$.
</s>