2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ The $\times$, the $Res_{w=0}$ and $[z^{n-1}]$ are all special notations, aren't they? $\endgroup$ – Sudix Jul 14 at 22:53
  • $\begingroup$ Wikipedia has an entry on extracting coefficients of formal power series and an entry on complex residues. $\endgroup$ – Marko Riedel Jul 15 at 15:22
  • 1
    $\begingroup$ 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. $\endgroup$ – Marko Riedel Jul 15 at 15:59
  • 1
    $\begingroup$ @MarkoRiedel: Impressive and instructive derivation. Verified. (+1) $\endgroup$ – Markus Scheuer Jul 16 at 4:46
  • 1
    $\begingroup$ 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. $\endgroup$ – Marko Riedel Jul 16 at 12:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user Jul 8 at 5:56
  • $\begingroup$ 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$$ $\endgroup$ – Peter Taylor Jul 8 at 6:41
  • $\begingroup$ I agree with WA definition $$\binom{-1}{-2}=-1.$$ Then the sum evaluates to 0. $\endgroup$ – user Jul 8 at 6:49

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.