Proving an interesting binomial sum 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?
 A: 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)$.
A: Theorem: If $f$ is a polynomial of degree $n$ or less,
$$
\sum_{k=0}^n(-1)^k\binom{n}{k}\frac{f(k)}{x+k}=\frac{n!f(-x)}{x(x+1)(x+2)\cdots(x+n)}\tag1
$$
Proof: Use the Heaviside Method for Partial Fractions: to get the coefficient for $\frac1{x+k}$ multiply by $x+k$ and set $x=-k$:
$$
\frac{n!f(k)}{\underbrace{(-k)(-k+1)(-k+2)\cdots(-1)}_{(-1)^kk!}\underbrace{(1)\cdots(-k+n)}_{(n-k)!}}=(-1)^k\binom{n}{k}f(k)\tag2
$$
$\large\square$
We also have
$$
\begin{align}
\binom{2n-2k}{n-k}\binom{n-k}{k}
&=\binom{2n-2k}{n-k}\binom{n-k}{n-2k}\tag{3a}\\
&=\binom{2n-2k}{n-2k}\binom{n}{k}\tag{3b}\\
&=\binom{2n-2k}{n}\binom{n}{k}\tag{3c}\\
\end{align}
$$
Explanation:
$\text{(3a):}$ $\binom{a}{b}=\binom{a}{a-b}$ (symmetry of Pascal's Triangle)
$\text{(3b):}$ $\binom{a}{b}\binom{b}{c}=\binom{a}{c}\binom{a-c}{b-c}$ (expand as ratios of factorials)
$\text{(3c):}$ $\binom{a}{b}=\binom{a}{a-b}$ (symmetry of Pascal's Triangle)
Since $f(x)=\frac12\binom{2n-2x}{n}$ is a polynomial of degree $n$, we can apply $(1)$ with $x=\frac12$:
$$
\begin{align}
\sum_{k=0}^n\frac{(-1)^k}{\color{#C00}{2k+1}}\color{#090}{\binom{2n-2k}{n-k}\binom{n-k}{k}}
&=\sum_{k=0}^n\frac{(-1)^k}{\color{#C00}{k+\frac12}}\color{#C00}{\frac12}\color{#090}{\binom{2n-2k}{n}\binom{n}{k}}\tag{4a}\\
&=\frac{n!\frac12\binom{2n+1}{n}}{\frac12\frac32\frac52\cdots\frac{2n+1}2}\tag{4b}\\
&=\frac{n!\binom{2n+1}{n}}{\frac{(2n+1)!}{4^nn!}}\tag{4c}\\[3pt]
&=\frac{4^n}{n+1}\tag{4d}
\end{align}
$$
Explanation:
$\text{(4a):}$ apply $(3)$
$\text{(4b):}$ apply $(1)$ with $x=\frac12$ and $f(x)=\frac12\binom{2n-2x}{n}$
$\text{(4c):}$ cancel the $\frac12$ in the numerator and denominator
$\phantom{\text{(4c):}}$ and write the denominator in terms of factorials
$\text{(4d):}$ simplify
