I am trying to prove the binomial identity
$$\sum_{k = 0}^n \frac{(-1)^k}{2k+1} \binom{2n – 2k}{n-k} \binom{n – k}{k} = \frac{4^n}{n+1},$$
without using induction. Here $n$ is a non-negative integer. The factor of $2k + 1$ in the denominator suggests one try to integrate $x^{2k}$ between the limits of $0$ and $1$. To do this one would need to know what
$$\sum_{k = 0}^n (-1)^k \binom{2n – 2k}{n – k} \binom{n – k}{k} x^{2k},$$
is in closed-form. It seems to involve (according to Mathematica) some hypergeometric function, the integral of which is by no means obvious.
I have also tried coefficient extraction methods $[z^n]$, but again the factor of $2k + 1$ in the denominator makes this problematic (at least for me).
So my question is, given the simple form of the expression on the right of this identity, is there a relatively easy way to prove this identity? Perhaps there is some simple trick I am missing?
Best Answer
That's simple if you recognize Legendre polynomials hidden in such sum. We have
$$ P_n(x) = \frac{1}{2^n}\sum_{k=0}^{\lfloor n/2\rfloor}(-1)^k\binom{n}{k}\binom{2n-2k}{n}x^{n-2k}\stackrel{\text{Rodrigues}}{=}\frac{1}{2^n n!}\cdot\frac{d^n}{dx^n}(x^2-1)^n \tag{1}$$ while
$$ S(n)=\sum_{k=0}^{\lfloor{n/2}\rfloor}\frac{(-1)^k}{2k+1}\binom{2n-2k}{n-k}\binom{n-k}{k}=\sum_{k=0}^{\lfloor{n/2}\rfloor}\frac{(-1)^k}{2k+1}\binom{n}{k}\binom{2n-2k}{n}\tag{2}$$ so
$$ S(n) = 2^n\int_{0}^{1}x^n P_n(1/x)\,dx =2^n \int_{1}^{+\infty}\frac{P_n(x)}{x^{n+2}}\,dx.\tag{3}$$ This allows to recover the generating function for $S(n)$ from the generating function of $P_n(x)$.
By multiplying both sides of $(3)$ by $z^n$ and summing over $n\geq 0$ we have $$\begin{eqnarray*} \sum_{n\geq 0} S(n) z^n &=& \int_{1}^{+\infty}\frac{dx}{x \sqrt{(1-4z)x^2+4z^2}}\\&=&\frac{1}{2z}\operatorname{arcsinh}{\frac{2z}{\sqrt{1-4z}}}\\&=&\frac{1}{2z}\operatorname{arctanh}\left(\frac{2z}{1-2z}\right)=\frac{-\ln(1-4z)}{4z}\end{eqnarray*}\tag{4}$$ and the claim readily follows from the Maclaurin series of the RHS of $(4)$.