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

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.

• A closed hypergeometric identity like this can always be proved by induction if you have no better ideas. – Peter Taylor Dec 20 '18 at 14:28

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; 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.

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!}.}$$

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.

• Thank you for your explanation! It seems like this was particularly easy to prove for you. Could you maybe give a similar formula for $\sum_{k=m}^n{2n+1\choose 2k}{k\choose k-m}$? – Mastrem Dec 21 '18 at 18:51
• Just type it into Wolfram Alpha -- wolframalpha.com/input/… – ablmf Dec 21 '18 at 18:55
• Of course! thanks again – Mastrem Dec 21 '18 at 19:02