binomial-coefficientscalculuscombinatoricshypergeometric function
I came across this nice binomial identity
$${\sum}_{k=0}^{2n} \frac{(-1)^k {2n \choose k} {2k \choose k}}{n+k \choose k} = 1$$
This is equivalent to the hypergeometric function ${}_2 F_1(-2n, 1/2; n+1; 4)$. I am having a hard time trying to prove this. Can someone help me with a hint to prove this?
$$ \begin{align} \sum_{k=0}^{\infty} \frac{(-1)^k}{(2k+1)^2}\frac{4^k}{{2k \choose k}} &= \sum_{k=0}^{\infty} \frac{(-1)^{k}}{2k+1} \int_{0}^{\pi /2} \sin^{2k+1} (x) \, dx \\ &= \int_{0}^{\pi /2} \sum_{n=0}^{\infty} \frac{(-1)^{k} \sin^{2k+1} (x)}{2k+1} \, dx\\ &= \int_{0}^{\pi /2} \arctan (\sin x) \, dx \\ &= \int_{0}^{1} \frac{\arctan t}{\sqrt{1-t^{2}}} \, dt \end{align}$$
Let $ \displaystyle I(a) = \int_{0}^{1} \frac{\arctan (at)}{\sqrt{1-t^{2}}} \ dt$.
Then differentiating under the integral sign,
$$ \begin{align} I'(a) &= \int_{0}^{1} \frac{t}{(1+a^{2}t^{2})\sqrt{1-t^{2}}} \, dt \\ &= \int_{0}^{1} \frac{1}{[1+a^{2}(1-u^{2})]u} \, u \, du \\ &= \frac{1}{1+a^{2}} \int_{0}^{1} \frac{1}{1-\left( \frac{au}{\sqrt{1+a^{2}}}\right)^{2}} \, du \\ &= \frac{1}{a \sqrt{1+a^{2}}} \text{arctanh} \left( \frac{a}{\sqrt{1+a^{2}}} \right) \\ &= \frac{1}{a\sqrt{1+a^{2}}} \frac{1}{2} \ln \Big((a+\sqrt{1+a^{2}})^{2} \Big) \\ &= \frac{1}{a \sqrt{1+a^{2}}} \ln \left( a+ \sqrt{1+a^{2}} \right) \\ &= \frac{1}{a \sqrt{1+a^{2}}} \text{arcsinh}(a) . \end{align}$$
And then integrating back,
$$ \begin{align} I(1)-I(0) = I(1) &= \int_{0}^{1} \frac{\text{arcsinh}(a)}{a \sqrt{1+a^{2}}} \, da \\ &= - \text{arcsinh}(a) \text{arcsinh}(\frac{1}{a}) \Bigg|^{1}_{0} + \int_{0}^{1} \frac{\text{arcsinh}(\frac{1}{a})}{\sqrt{1+a^{2}}} \, da \\ &= - \text{arcsinh}^{2}(1) + \int_{0}^{1} \frac{\text{arcsinh}(\frac{1}{a})}{\sqrt{1+a^{2}}} \, da \\ &= - \ln^{2}(1+\sqrt{2}) + \int_{0}^{1} \frac{\text{arcsinh}(\frac{1}{a})}{\sqrt{1+a^{2}}} \, da . \end{align}$$
Now let $ \displaystyle w = \frac{1}{a}$.
Then
$$ I(1) = - \ln^{2}(1+\sqrt{2}) + \int_{1}^{\infty} \frac{\text{arcsinh}(w)}{w \sqrt{1+w^{2}}} \, dw$$
$$ = - \ln^{2}(1+\sqrt{2}) + I(\infty) - I(1) .$$
Therefore,
$$ \begin{align} I(1) &= - \frac{\ln^{2}(1+\sqrt{2})}{2} + \frac{I(\infty)}{2} \\ &= - \frac{\ln^{2}(1+\sqrt{2})}{2} + \frac{\pi}{4} \int_{0}^{1} \frac{1}{\sqrt{1-t^{2}}} \, dt \\ &= - \frac{\ln^{2}(1+\sqrt{2})}{2} + \frac{\pi^{2}}{8} . \end{align}$$
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.
Best Answer
Let $F(n,k)=(-1)^k\binom{2n}k\binom{2k}{k}\big/\binom{n+k}{k}$ be the summand, and let $S_n=\sum_{k=0}^{2n}F(n,k)$ be the sum to be computed. Let $$ G(n,k)=(-1)^k\binom{2n}{k-2}\binom{2k}{k}\Big/\binom{n+k}{k}. $$ You can show, through tedious algebraic manipulations alone, that for all $n,k\ge 0$, $$ 3(F(n,k)-F(n+1,k))=G(n,k+1)-G(n,k).\tag{*} $$ Specifically, write both sides in terms of factorials, then cancel common factorial terms until all that remains is a rational equation in $n,k$, which can be proven by clearing denominators and polynomial manipulation.
Summing both sides of $(*)$ from $k=0$ to $2n+2$, you get that $$ 3S_{n}-3S_{n+1}=G(n,2n+3)-G(n,0)=0-0=0. $$ This proves that $S_{n}$ is independent of $n$, so you need only verify that $S_0=1$ to prove $S_n=1$ for all $n$.
If you are wondering where $G(n,k)$ came from, it is of the form $G(n,k)=F(n,k)\cdot R(n,k),$ where $$R(n,k)=k(k-1)/(2n-k+1)(2n-k+2),$$ after canceling some common factors, necessary to prevent division by zero. This function $R(n,k)$ which causes $(*)$ to be satisfied can be found using Zeilberger's algorithm. For example, in Maxima, you can use the commands
to get both the coefficients $[3,-3]$ on the LHS of $(*)$, and $R(n,k)$. You can see for yourself by copy pasting those commands into this online Maxima compiler.
My purpose in including this explanation is to help spread the word that a proof of "any" summation identity with binomial coefficients can be found automatically with the right computer program. For anyone who encounters complicated binomial summations like this a lot, this power is very desirable! In fact, if you only have the summation, you can determine if a closed form exists using the same algorithm. The exact requirements on the "any" part are described in the book $A = B$, available for free online: A = B on Herbert Wilf's website. This is a must-read for anyone who wants this power.