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.

  • $\begingroup$ A closed hypergeometric identity like this can always be proved by induction if you have no better ideas. $\endgroup$ – 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<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.


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.

  • $\begingroup$ 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}$? $\endgroup$ – Mastrem Dec 21 '18 at 18:51
  • $\begingroup$ Just type it into Wolfram Alpha -- wolframalpha.com/input/… $\endgroup$ – ablmf Dec 21 '18 at 18:55
  • $\begingroup$ Of course! thanks again $\endgroup$ – Mastrem Dec 21 '18 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.