Prove $\sum_{k=m}^n{k\choose k-m}{2n\choose 2k}=4^{n-m}\frac{n(2n-m-1)!}{(2n-2m)!m!}.$

Question

For $n\in\mathbb{Z}_{\ge 1}$ and $m\in\{0,1,\ldots,n\}$ I'd like to prove $$\sum_{k=m}^n{k\choose k-m}{2n\choose 2k}=4^{n-m}\frac{n(2n-m-1)!}{(2n-2m)!m!}.$$ Though I've confirmed the identity for all $n\le 20$, sadly I don't have a proof.

Answer 1

Nowadays it is a matter of machinery.

For a pencil-and-paper approach... the sum is equal to the coefficient of $x^{2n}$ in $$\left(\sum_{k=m}^{\infty}\binom{k}{k-m}x^{2k}\right)\left(\sum_{k=0}^{2n}\binom{2n}{k}x^k\right)=\frac{x^{2m}}{(1-x^2)^{m+1}}(1+x)^{2n}=\frac{x^{2m}(1+x)^{2n-m-1}}{(1-x)^{m+1}}$$ which, by Cauchy integral formula, is equal to $$\frac{1}{2\pi i}\oint_{|z|=r}\frac{(1+z)^{2n-m-1}\,dz}{z^{2n-2m+1}(1-z)^{m+1}}=\frac{1}{2\pi i}\oint_{|w|=1/r}\frac{w(w+1)^{2n-m-1}}{(w-1)^{m+1}}dw$$ (where $0<r<1$; the latter is obtained by substitution $z=1/w$).

Thus it is the coefficient of $z^m$ in $(z+1)(z+2)^{2n-m-1}$, equal to $$2^{2n-2m-1}\binom{2n-m-1}{m}+2^{2n-2m}\binom{2n-m-1}{m-1},$$ which simplifies exactly to your formula.

Answer 2

I upvoted the accepted answer for its instructive management of the poles (pole at zero disappears due to substitution but a pole at one appears inside the substituted contour and the power series at one is particularly easy to find). What follows uses formal power series and a different substitution and documents all the steps. Let's start with

$$\sum_{k=m}^n {k\choose k-m} {2n\choose 2k} = \sum_{k=m}^n {k\choose k-m} {2n\choose 2n-2k} \\ = \sum_{k=m}^n {k\choose k-m} [z^{2n-2k}] (1+z)^{2n} = [z^{2n}] (1+z)^{2n} \sum_{k=m}^n {k\choose k-m} z^{2k}.$$

Now we may certainly extend $k$ beyond $n$ because there is no contribution to $[z^{2n}]$ in that case. We get

$$[z^{2n}] (1+z)^{2n} \sum_{k\ge m} {k\choose k-m} z^{2k} = [z^{2n}] (1+z)^{2n} z^{2m} \sum_{k\ge 0} {k+m\choose k} z^{2k} \\ = [z^{2n-2m}] (1+z)^{2n} \frac{1}{(1-z^2)^{m+1}} = [z^{2n-2m}] (1+z)^{2n-m-1} \frac{1}{(1-z)^{m+1}}.$$

This is

$$\mathrm{Res}_{z=0} \frac{1}{z^{2n-2m+1}} (1+z)^{2n-m-1} \frac{1}{(1-z)^{m+1}}.$$

The subsitution $z/(1+z) = w$ or $z=w/(1-w)$ now yields

$$\mathrm{Res}_{w=0} \frac{1}{w^{2n-2m+1}} \frac{1}{(1-w)^{m-2}} \frac{(1-w)^{m+1}}{(1-2w)^{m+1}} \frac{1}{(1-w)^2} \\ = \mathrm{Res}_{w=0} \frac{1}{w^{2n-2m+1}} \frac{1-w}{(1-2w)^{m+1}}.$$

This is

$$[w^{2n-2m}] \frac{1-w}{(1-2w)^{m+1}} = [w^{2n-2m}] \frac{1}{(1-2w)^{m+1}} - [w^{2n-2m-1}] \frac{1}{(1-2w)^{m+1}} \\ = 2^{2n-2m} {2n-m\choose m} - 2^{2n-2m-1} {2n-m-1\choose m} \\ = 4^{n-m} \frac{(2n-m-1)!}{(2n-2m)! m!} \left(2n-m - \frac{1}{2} (2n-2m)\right).$$

which is indeed

$$\bbox[5px,border:2px solid #00A000]{ n 4^{n-m} \frac{(2n-m-1)!}{(2n-2m)! m!}.}$$

Answer 3

As mentioned by metamorphy, this can be done completely with machines now. So basically you do not have to prove it, a few lines of machine code can do it for you.

In the following, I will explain how CAS can prove this using creative telescoping algorithms.

The package that I used is called Sigma.

First the left-hand-side can be written as $$ S(n_0)=\underset{k=0}{\overset{n_0}{\sum }} f(n_0,k) $$ where $n_0=n-m$ and $$ f(n_0,k)= \left( \begin{array}{c} k+m \\ k \\ \end{array} \right) \left( \begin{array}{c} 2 \left(m+n_0\right) \\ 2 (k+m) \\ \end{array} \right) . $$ Next, let $$ c_0(n)=2 (1 + m + n_0) (m + 2 n_0) (1 + m + 2 n_0), $$ and $$ c_1(n)=-(1 + n_0) (m + n_0) (1 + 2 n_0) $$ and $$ g(n_0,k)=-\frac{k (2 k+2 m-1) \left(m+n_0+1\right) \binom{k+m}{k} \left(2 k m+4 k n_0+2 k-4 m n_0-3 m-6 n_0^2-7 n_0-2\right) \binom{2 m+2 n_0}{2 k+2 m}}{\left(2 k-2 n_0-1\right) \left(k-n_0-1\right)}. $$ Then you can verify in your favorite CAS system that $$ g\left(n_0,k+1\right)-g\left(n_0,k\right)=c_0\left(n_0\right) f\left(n_0,k\right)+c_1\left(n_0\right) f\left(n_0+1,k\right) . $$ This recursion is found by using the Mathematica package Sigma. This is where the computer becomes most useful--they find these recursions for you.

Now we sum over $k=1,..n_0-1$, we get. $$ c_0(n_0) S\left(n_0\right)+c_1(n_0) S\left(n_0+1\right)=0 . $$

This is a simple recursion, plugin $S(0)=f(0,0)=1$, we get $$ S(n_0)= \frac{4^{n_0} \left(m+n_0\right) \left(m+2 n_0-1\right)!}{m! \left(2 n_0\right)!} = \frac{n 4^{n-m} (-m+2 n-1)!}{m! (2 n-2 m)!} . $$ where we substitute by $n_0=n-m$. This is exactly the right-hand-side.