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? 
 A: Using the integral representation of the binomial coefficient $$\dbinom{s}{k}=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{s}}{z^{k+1}}dz$$ we have
 $$ \sum_{k=1}^{n}k\dbinom{m+k}{m+1}=\frac{1}{2\pi i}\sum_{k=1}^{n}k\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{m+k}}{z^{m+2}}dz
 $$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{m}}{z^{m+2}}\sum_{k=1}^{n}k\left(1+z\right)^{k}dz
 $$ $$=\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{m+n+1}}{z^{m+4}}\left(nz-1\right)dz+\frac{1}{2\pi i}\oint_{\left|z\right|=1}\frac{\left(1+z\right)^{m+1}}{z^{m+4}}dz$$ $$
 =n\dbinom{m+n+1}{m+2}-\dbinom{m+n+1}{m+3}
 $$ which is equivalent to your claim. To see that we have the same result, note that holds $$\dbinom{n}{k}=\frac{n+1-k}{k}\dbinom{n}{k-1}.$$
A: For  those who  enjoy integrals  here  is another  approach using  the
Egorychev method as  presented in many posts by  @FelixMarin and also by @MarkusScheuer, where we focus on finding an answer  that differs from the approaches that have already been seen.
Suppose we seek to compute
$$S(n,m) = \sum_{k=0}^n k{m+k\choose m+1}.$$
Introduce
$${m+k\choose m+1}
= \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m+k} \; dz$$
as well as the Iverson bracket
$$[[0\le k\le n]]
= \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{w^k}{w^{n+1}} \frac{1}{1-w} \; dw.$$
This yields for the sum
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m} 
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n+1}} \frac{1}{1-w} 
\sum_{k\ge 0} k w^k (1+z)^k
\; dw \; dz.$$
For this to converge we must have $|w(1+z)|<1.$ We get
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m} 
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n+1}} \frac{1}{1-w} 
\frac{w(1+z)}{(1-w(1+z))^2}
\; dw \; dz
\\ = \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m+1} 
\frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n}} \frac{1}{1-w} 
\frac{1}{(1-w(1+z))^2}
\; dw \; dz.$$
We evaluate the inner integral using the fact that the residues at the
poles sum to zero. The residue at $w=1$ produces
$$-\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m+1} 
\frac{1}{(-z)^2} \; dz
= -\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+4}} (1+z)^{m+1} \; dz
= 0.$$
For the residue at $w=1/(1+z)$ we re-write the inner integral to get
$$\frac{1}{(1+z)^2} \frac{1}{2\pi i}
\int_{|w|=\gamma}
\frac{1}{w^{n}} \frac{1}{1-w} 
\frac{1}{(w-1/(1+z))^2}
\; dw.$$
We thus require
$$\left.\left(\frac{1}{w^{n}} 
\frac{1}{1-w}\right)'\right|_{w=1/(1+z)}
\\ = \left. \left(\frac{-n}{w^{n+1}} \frac{1}{1-w}
+ \frac{1}{w^n} \frac{1}{(1-w)^2}\right) \right|_{w=1/(1+z)}
\\ = -n (1+z)^{n+1} (1+z)/z + (1+z)^n (1+z)^2/z^2.$$
Substituting this  into the outer  integral and flipping signs  we get
two pieces which are
$$\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m-1} n(1+z)^{n+2}/z \; dz
\\ = \frac{n}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+3}} (1+z)^{n+m+1} \; dz
= n\times {n+m+1\choose m+2}.$$
The second piece is
$$- \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+2}} (1+z)^{m-1}(1+z)^{n+2}/z^2 \; dz
\\ = - \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{m+4}} (1+z)^{n+m+1} \; dz
= - {n+m+1\choose m+3}.$$
It follows that our answer is
$$\left(n - \frac{n-1}{m+3}\right) {n+m+1\choose m+2}
= \frac{nm+2n+1}{m+3} {n+m+1\choose m+2}.$$
Remark. Being rigorous we also verify that the residue at infinity
in the calculation of the inner integral is zero. We get
$$-\mathrm{Res}_{w=0} \frac{1}{w^2}
w^{n} \frac{1}{1-1/w} \frac{1}{(1-(1+z)/w)^2}
\\ = - \mathrm{Res}_{w=0} 
w^{n-2} \frac{w}{w-1} \frac{w^2}{(w-(1+z))^2}
= - \mathrm{Res}_{w=0} 
\frac{w^{n+1}}{w-1} \frac{1}{(w-(1+z))^2}.$$
There is  certainly no pole  at zero here  and the residue is  zero as
claimed (the  term $1+z$ rotates in  a circle around the  point one on
the real axis  and with $\epsilon \lt 1$ it is  never zero). This last
result could  also be obtained  by comparing degrees of  numerator and
denominator.
A: 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*}
$$
A: The series can also be seen as the following.
\begin{align}
\sum_{k=0}^{n} k \, \binom{m+k}{m+1} &= \frac{1}{m+1} \, \sum_{k=0}^{n} k \, \frac{(m+1)_{k}}{k!} \\
&= \frac{1}{m+1} \, \left[ \sum_{k=0}^{n-2} \frac{(m+1)_{k+2}}{k!} + \sum_{k=0}^{n-1} \frac{(m+1)_{k+1}}{k!} \right] \\
&= (m+2) \, \frac{(n-1) \, \Gamma(m+n+2)}{\Gamma(n) \, \Gamma(m+4)} + \frac{ \Gamma(m+n+2)}{\Gamma(n) \, \Gamma(m+3)} \\
&= \frac{(m+n+1)!}{(n-1)! \, (m+3)!} \, (m \, n + 2n + 1) \\
&= \frac{m \, n + 2n + 1}{m+3} \, \binom{m+n+1}{n-1}. 
\end{align}
Rearranging terms yields the form presented in the proposed problem. The notation used in Pochhammer's notation, namely,
\begin{align}
(x)_{k} = \frac{\Gamma(x+k)}{\Gamma(x)}.
\end{align}
A: Here is a slightly different variation of the theme. It is convenient to use the coefficient of operator $[x^k]$ to denote the coefficient of $x^k$ of a series. This way we can write e.g.
\begin{align*}
[x^k](1+x)^n=\binom{n}{k}\tag{1}
\end{align*}

We obtain
  \begin{align*}
\sum_{k=1}^{n}&k\binom{m+k}{m+1}=\sum_{k=1}^nk[x^{m+1}](1+x)^{m+k}\tag{2}\\
&=[x^{m+1}](1+x)^{m+1}\sum_{k=1}^nk(1+x)^{k-1}\tag{3}\\
&=[x^{m+1}](1+x)^{m+1}D_x\left(\sum_{k=1}^n(1+x)^{k}\right)\tag{4}\\
&=[x^{m+1}](1+x)^{m+1}D_x\left(\frac{1-(1+x)^{n+1}}{1-(1+x)}-1\right)\tag{5}\\
&=[x^{m+1}](1+x)^{m+1}\left(\frac{(nx-1)(1+x)^n}{x^2}+\frac{1}{x^2}\right)\tag{6}\\
&=[x^{m+3}](1+x)^{m+n+1}(nx-1)\tag{7}\\
&=n[x^{m+2}](1+x)^{m+n+1}-[x^{m+3}](1+x)^{m+n+1}\tag{8}\\
&=n\binom{m+n+1}{m+2}-\binom{m+n+1}{m+3}\tag{9}
\end{align*}

Comment:


*

*In (2) we apply the coefficient of operator according to (1)

*In (3) we use the linearity of the coefficient of operator and split the binomial conveniently

*In (4) we introduce the differential operator $D_x:=\frac{d}{dx}$ 

*In (5) we use the formula for the finite geometric series

*In (6) we apply the differential operator $D_x$

*In (7) we do some simplifications and use the rule
\begin{align*}
[x^m]x^{-k}A(x)=[x^{m+k}]A(x)
\end{align*}

*In (8) we use the linearity of the coefficient of operator and apply the rule above again

*In (9) we write the expression using binomial coefficients and obtain a result in accordance with the answer of @MarcoCantarini
