Magic sum with binomial coefficient

Question

Mathematica gives to me the following relation for every fixed $m,n\geq1$

$$\sum_{k=1}^n\frac {(2n-k-1)!\cdot k}{(n-k)!} {{m+k}\choose{m}} =\frac{(m+1)(m+2n)!}{(m+n+1)!}$$

Any hint for the proof?

Answer 1

We obtain \begin{align*} \color{blue}{\sum_{k=1}^n}&\color{blue}{\frac{(2n-k-1)!k}{n!(n-k)!}\binom{m+k}{m}}\\ &=\frac{m+1}{n}\sum_{k=1}^{n}\binom{2n-1-k}{n-k}\binom{m+k}{k-1}\tag{1}\\ &=\frac{m+1}{n}\sum_{k=1}^n\binom{-n}{n-k}(-1)^{n-k}\binom{-m-2}{k-1}(-1)^{k-1}\tag{2}\\ &=(-1)^{n-1}\frac{m+1}{n}\sum_{k=0}^{n-1}\binom{-n}{n-1-k}\binom{-m-2}{k}\tag{3}\\ &=(-1)^{n-1}\frac{m+1}{n}\binom{-n-m-2}{n-1}\tag{4}\\ &=\frac{m+1}{n}\binom{m+2n}{n-1}\tag{5}\\ &\,\,\color{blue}{=\frac{(m+1)(m+2n)!}{n!(m+n+1)!}} \end{align*} and the claim follows.

Comment:

• In (1) we write the factorials using binomial coefficients and use the binomial identity $\binom{p}{q}=\frac{p-q}{q}\binom{p}{q-1}$.

• In (2) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$.

• In (3) we shift the index by one to start with $k=0$.

• In (4) we apply the Chu-Vandermonde identity.

• In (5) we apply the binomial identity $\binom{-p}{q}=\binom{p+q-1}{q}(-1)^q$ again.