# A combinatorial identity involving square of central binomial coefficient.

While solving a problem I came across the following interesting identity, valid by numerical evidence: $$S_n:=\sum_{k=0}^n\left (-\frac14\right)^k\binom {2k}k^2\frac1 {1-2k}\binom {n+k-2}{2k-2}=\begin {cases}\displaystyle \left [ \left (\frac14\right)^m\binom {2m}m\frac1 {1-2m}\right]^2,& n=2m;\\ 0,& n=2m+1. \end{cases}\tag1$$ Is there a simple way to prove it?

From WA I know: $$S_n=\frac {(1-(-1)^n)\Gamma^2 (\frac {n-1}2)}{8\pi\Gamma^2 (\frac {n+2}2)}\tag2$$ Obviously (2) evaluates to 0 for odd $$n$$. For $$n=2m$$ the expression gives $$S_{2m}=\frac {\Gamma^2 (m-\frac12)}{4\pi\Gamma^2 (m+1)}=\frac {\left [\frac {(2m-2)!}{(m-1)!}\frac{\sqrt\pi}{4^{m-1}}\right]^2}{4\pi (m!)^2}\\ =4\left [\frac1 {4^{m}}\frac{m} {(2m)(2m-1)}\frac {(2m)!}{m!m!}\right]^2 =\left [\frac1 {4^{m}}\frac{1} {2m-1}\binom {2m}{m}\right]^2,$$ also in agreement with (1).

However I still wonder how the result can be obtained without resorting to computer help.

• Have you tried Zeilberger's algorithm? – Peter Taylor Jul 7 at 8:22
• @PeterTaylor No. I am not experienced in this technique and will be very thankful for any hint. – user Jul 7 at 19:26

Starting from (the contribution from $$k=0$$ is zero owing to the third binomial coefficient)

$$\sum_{k=1}^n \left(-\frac{1}{4}\right)^k {2k\choose k}^2 \frac{1}{1-2k} {n+k-2\choose 2k-2}$$

we seek to show that this is zero when $$n$$ is odd and

$$\left[\left(\frac{1}{4}\right)^m {2m\choose m} \frac{1}{1-2m}\right]^2$$

when $$n=2m$$ is even.

We observe that with $$k\ge 1$$

$${2k\choose k} \frac{1}{1-2k} {n+k-2\choose 2k-2} = 2 {2k-1\choose k-1} \frac{1}{1-2k} {n+k-2\choose 2k-2} \\ = -2 {2k-2\choose k-1} \frac{1}{k} {n+k-2\choose 2k-2} = -\frac{2}{k} \frac{(n+k-2)!}{(k-1)!^2 \times (n-k)!} \\ = -\frac{2}{k} {n+k-2\choose k-1} {n-1\choose k-1} = -\frac{2}{n} {n\choose k} {n+k-2\choose k-1}.$$

We get for our sum

$$-\frac{2}{n} \sum_{k=1}^n {n\choose k} \left(-\frac{1}{4}\right)^k {2k\choose k} {n+k-2\choose k-1} \\ = -\frac{2}{n} \sum_{k=1}^n {n\choose k} {-1/2\choose k} {n+k-2\choose n-1} \\ = -\frac{2}{n} [z^{n-1}] (1+z)^{n-2} \sum_{k=1}^n {n\choose k} {-1/2\choose k} (1+z)^k.$$

The value $$k=0$$ contributes zero:

$$-\frac{2}{n} \times \mathrm{Res}_{w=0} \frac{1}{w} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} \sum_{k=0}^n {n\choose k} \frac{1}{w^k} (1+z)^k \\ = -\frac{2}{n} \times \mathrm{Res}_{w=0} \frac{1}{w} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} (1+(1+z)/w)^n \\ = -\frac{2}{n} \times \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} (1+w+z)^n \\ = -\frac{2}{n} \times \mathrm{Res}_{w=0} \frac{1}{w^{n+1}} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} \sum_{q=0}^n {n\choose q} (1+w)^q z^{n-q} \\ = -\frac{2}{n} \times \sum_{q=1}^n {n\choose q} {q-1/2\choose n} {n-2\choose q-1}.$$

Now observe that with $$q\lt n$$ (third binomial coefficient is zero when $$q=n$$)

$${q-1/2\choose n} = \frac{1}{n!} (q-1/2)^\underline{n} = \frac{1}{n!} \prod_{p=0}^{q-1} (q-1/2-p) \prod_{p=q}^{n-1} (q-1/2-p) \\ = \frac{1}{n! \times 2^n} \prod_{p=0}^{q-1} (2q-1-2p) \prod_{p=q}^{n-1} (2q-1-2p) \\ = \frac{1}{n! \times 2^n} \frac{(2q-1)!}{(q-1)! \times 2^{q-1}} \prod_{p=0}^{n-1-q} (-1-2p) \\ = \frac{(-1)^{n-q}}{n! \times 2^n} \frac{(2q-1)!}{(q-1)! \times 2^{q-1}} \frac{(2n-1-2q)!}{(n-1-q)! \times 2^{n-1-q}} \\= \frac{(-1)^{n-q}}{2^{2n-2}} {n\choose q}^{-1} {2q-1\choose q-1} {2n-1-2q\choose n-q}.$$

We get for our sum

$$-\frac{1}{n \times 2^{2n-3}} \times \sum_{q=1}^{n-1} (-1)^{n-q} {2q-1\choose q-1} {2n-1-2q\choose n-q} {n-2\choose q-1} \\ = \frac{1}{n \times 2^{2n-3}} \times \sum_{q=0}^{n-2} {n-2\choose q} (-1)^{n-2-q} {2q+1\choose q} {2n-3-2q\choose n-q-1}.$$

This becomes

$$\frac{1}{n \times 2^{2n-3}} \times [z^{n-1}] (1+z)^{2n-3} \sum_{q=0}^{n-2} {n-2\choose q} (-1)^{n-2-q} {2q+1\choose q} z^q (1+z)^{-2q} \\ = \frac{1}{n \times 2^{2n-3}} \mathrm{Res}_{w=0} \frac{1+w}{w} [z^{n-1}] (1+z)^{2n-3} \\ \times \sum_{q=0}^{n-2} {n-2\choose q} (-1)^{n-2-q} \frac{1}{w^{q}} (1+w)^{2q} z^q (1+z)^{-2q} \\ = \frac{1}{n \times 2^{2n-3}} \mathrm{Res}_{w=0} \frac{1+w}{w} [z^{n-1}] (1+z)^{2n-3} \left(\frac{z(1+w)^2}{w(1+z)^2}-1\right)^{n-2} \\ = \frac{1}{n \times 2^{2n-3}} \mathrm{Res}_{w=0} \frac{1+w}{w^{n-1}} [z^{n-1}] (1+z) \left(z(1+w)^2-w(1+z)^2\right)^{n-2} \\ = \frac{1}{n \times 2^{2n-3}} \mathrm{Res}_{w=0} \frac{1+w}{w^{n-1}} [z^{n-1}] (1+z) (z-w)^{n-2} (1-wz)^{n-2}.$$

The first piece in $$z$$ is

$$[z^{n-1}] (z-w)^{n-2} (1-wz)^{n-2} \\ = \sum_{q=1}^{n-2} {n-2\choose q} (-1)^{n-2-q} w^{n-2-q} {n-2\choose n-1-q} (-1)^{n-1-q} w^{n-1-q} \\ = - \sum_{q=1}^{n-2} {n-2\choose q} {n-2\choose q-1} w^{2n-3-2q}.$$

Here we require

$$([w^{n-2}] + [w^{n-3}]) w^{2n-3-2q}$$

We get $$q=(n-1)/2$$ in the first case and $$q=n/2$$ in the second. As this is a pair of an integer and a fraction clearly only one of these extractors can return a non-zero value.

The second piece in $$z$$ is

$$[z^{n-2}] (z-w)^{n-2} (1-wz)^{n-2} \\ = \sum_{q=0}^{n-2} {n-2\choose q} (-1)^{n-2-q} w^{n-2-q} {n-2\choose n-2-q} (-1)^{n-2-q} w^{n-2-q} \\ = \sum_{q=0}^{n-2} {n-2\choose q} {n-2\choose q} w^{2n-4-2q}.$$

Solving for $$q$$ again we require

$$([w^{n-2}] + [w^{n-3}]) w^{2n-4-2q}$$

getting $$q=n/2-1$$ and $$q=(n-1)/2.$$

Supposing that $$n$$ is odd i.e. $$n=2m+1$$ we thus have

$$-{2m-1\choose m} {2m-1\choose m-1} + {2m-1\choose m} {2m-1\choose m} = 0,$$

and we have proved the second part of the claim. On the other hand with $$n=2m$$ even we collect

$$-{2m-2\choose m} {2m-2\choose m-1} + {2m-2\choose m-1} {2m-2\choose m-1} \\ = {2m-2\choose m-1}^2 \left(1 - \frac{m-1}{m}\right) = \frac{m^2} {(2m-1)^2} {2m-1\choose m}^2 \frac{1}{m} \\ = \frac{m^2} {(2m-1)^2} \frac{m^2}{(2m)^2} {2m\choose m}^2 \frac{1}{m} = \frac{1}{4} \frac{m} {(2m-1)^2} {2m\choose m}^2.$$

Restoring the factor in front we obtain

$$\frac{1}{n \times 2^{2n-3}} \frac{1}{4} \frac{m} {(2m-1)^2} {2m\choose m}^2 = \frac{1}{2^{2n}} \frac{1} {(2m-1)^2} {2m\choose m}^2 \\ = \frac{1}{2^{4m}} \frac{1} {(1-2m)^2} {2m\choose m}^2$$

This is

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

as was to be shown.

• The $\times$, the $Res_{w=0}$ and $[z^{n-1}]$ are all special notations, aren't they? – Sudix Jul 14 at 22:53
• Wikipedia has an entry on extracting coefficients of formal power series and an entry on complex residues. – Marko Riedel Jul 15 at 15:22
• Yes it is. There is an implicit parenthesis around everything that follows the times symbol which extends to the end of a multiline formula, thereby enforcing precedence. Also sometimes used for readability. – Marko Riedel Jul 15 at 15:59
• @MarkoRiedel: Impressive and instructive derivation. Verified. (+1) – Markus Scheuer Jul 16 at 4:46
• Thank you for the credit. The factorizations of ${q-1/2\choose n}$ and of $z(1+w)^2-w(1+z)^2$ were quite remarkable indeed, appearing in the same problem. – Marko Riedel Jul 16 at 12:44

In general, definite sums of binomial expressions (technically, hypergeometric terms) can be tackled by a technique called Zeilberger's algorithm. See the book $$A = B$$ by Petkovšek, Wilf, and Zeilberger. Used to be available legally online in PDF, and maybe still is somewhere.

The actual algorithm is complicated enough that it's better to implement it in a CAS than work it through by hand except in really trivial cases, but knowing its existence allows you to throw the sum at a CAS which implements it. In particular, Wolfram Alpha gave me

$$\sum_{k=0}^{2m+1} \frac{1}{(-4)^k (1 - 2k)} \binom{2k}{k}^2 \binom{2m+1+k-2}{2k-2} = \frac{\pi}{4\Gamma(1-m)^2 \Gamma\left(m+\frac32\right)^2}$$

which can be un-substituted to give

$$\sum_k \frac{1}{(-4)^k(1-2k)} \binom{2k}k^2 \binom{n+k-2}{2k-2} = \frac{\pi}{4\Gamma\left(\frac{3-n}2\right)^2 \Gamma\left(\frac{n+2}{2}\right)^2}$$

which looks like it's a good way towards your target. It also points up an exception to your case analysis: when $$n=1$$ the sum is non-zero.

• Thank yo very much. I have obtained with WA the result $$S_n=\frac{(1+(-1)^n)\Gamma^2(\frac{n-1}2)}{8\pi\Gamma^2(\frac{n+2}2)}$$ and still wonder if a human being is able to obtain the result without resorting to the computer help. But at least I know now the name of technique behind. Note the result is 0 for $n=1$ as well. – user Jul 8 at 5:56
• Zeilberger's algorithm can be done by hand, but it's tedious and error-prone. A homemade implementation could print the intermediate steps. For $n=1$ I evaluate the sum as $$\binom 00^2 \binom{-1}{-2} + \left(-\frac14\right) \binom 21^2 \frac1{1-2}\binom 00 =0+1$$ – Peter Taylor Jul 8 at 6:41
• I agree with WA definition $$\binom{-1}{-2}=-1.$$ Then the sum evaluates to 0. – user Jul 8 at 6:49