A combinatorial identity involving square of central binomial coefficient.

425 Views Asked by At

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.

2

There are 2 best solutions below

6
On BEST ANSWER

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\gt 1$ 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 \;\underset{w}{\mathrm{res}}\; \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 \;\underset{w}{\mathrm{res}}\; \frac{1}{w} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} (1+(1+z)/w)^n \\ = -\frac{2}{n} \times \;\underset{w}{\mathrm{res}}\; \frac{1}{w^{n+1}} (1+w)^{-1/2} [z^{n-1}] (1+z)^{n-2} (1+w+z)^n \\ = -\frac{2}{n} \times \;\underset{w}{\mathrm{res}}\; \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}} \;\underset{w}{\mathrm{res}}\; \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}} \;\underset{w}{\mathrm{res}}\; \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}} \;\underset{w}{\mathrm{res}}\; \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}} \;\underset{w}{\mathrm{res}}\; \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.

3
On

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.