<s>[INST] Evaluate an increasing sum of binomial coefficients: $\sum_{k=1}^nk\binom{m+k}{m+1}$ I've been working on a problem and got to a point where I need the closed form of 

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

I wasn't making any headway so I figured I would see what Wolfram Alpha could do. It gave me this: 
$$\sum_{k=1}^nk\binom{m+k}{m+1} = \frac{n((m+2)n+1)}{(m+2) (m+3)}\binom{m+n+1}{ m+1}.$$
That's quite the nasty formula. Can anyone provide some insight or justification for that answer? 
 [/INST] You can prove this by induction.
Here is the induction step:
$$
\begin{align*}
\sum_{k=1}^{n+1} k  \binom{m+k}{m+1} &= \frac{n((m+2)n+1)}{(m+2)(m+3)}\binom{m+n+1}{m+1} + (n+1)\binom{m+n+1}{m+1} \\
&=\frac{(m+n+2)(m(n+1)+2n+3)}{(m+2)(m+3)} \binom{m+n+1}{m+1} \\
&=\frac{(n+1)(m(n+1)+2n+3)}{(m+2)(m+3)} \cdot \frac{(m+n+2)!}{(m+1)!(n+1)!} \\
&= \frac{(n+1)((m+2)(n+1)+1)}{(m+2)(m+3)}\cdot \binom{m+n+2}{m+1}.
\end{align*}
$$
</s>