Evaluating $\sum\limits_{k=0}^n \frac{(-1)^k (4 n - 2 k)!}{k! (2 n - k)! (2 n - 2 k)! (2 n + 2 r + 1 - 2 k)}$ I'm trying to prove an property of Legendre polynomial, namely $\int_{-1}^1x^{2r}P_{2n}(x)dx=\frac{2^{2n+1}(2r)!(r+n)!}{(2r+2n+1)!(r-n)!}$
I'm required to use the general formula for Legendre polynomial,
 which is $\displaystyle P_{n}(x) = \sum_{r=0}^{[n/2]} \frac{(-1)^r (2n-2r)!}{2^n r! (n-r)! (n-2 r)!} x^{n-2 r}.$
So basically I need to show (I guess it may be possible using orthogonality, but not sure how to make it that way.)
$\displaystyle \sum_{k=0}^n \frac{(-1)^k (4 n - 2 k)!}{k! (2 n - k)! (2 n - 2 k)! (2 n + 2 r + 1 - 2 k)} = \frac{2^{4n}(2r)!(r+n)!}{(2r+2n+1)!(r-n)!}
$
When I plug in the sum expression into Wolfram alpha, it makes an output looks similar to RHS, so I guess there must be an algorithm to calculate such kind of sum.
Can anybody help me?
 A: We may safely assume $r\geq n$: otherwise we may write $x^{2r}$ as a linear combination of Legendre polynomials $P_k(x)$ with $k<2n$ and the outcome is zero by orthogonality. After this, in order to prove the first identity it is easier to exploit Rodrigues' formula and integration by parts:
$$\begin{eqnarray*} \int_{-1}^{1}x^{2r}P_{2n}(x)\,dx &=& \frac{1}{2^{2n}(2n)!}\int_{-1}^{1}x^{2r}\frac{d^{2n}}{dx^{2n}}(x^2-1)^{2n}\,dx\\(\text{IBP})\qquad&=&\frac{1}{2^{2n}(2n)!}\int_{-1}^{1}\frac{d^{2n}}{dx^{2n}}x^{2r}\cdot(x^2-1)^{2n}\,dx\\&=&\frac{1}{2^{2n}(2n)!}\int_{-1}^{1}\frac{(2r)!}{(2r-2n)!}x^{2r-2n}(x^2-1)^{2n}\,dx\\(\text{symmetry})\qquad&=&\frac{2}{4^n}\binom{2r}{2n}\int_{0}^{1}x^{2r-2n}(1-x^2)^{2n}\,dx\\(x^2\mapsto u)\qquad&=&\frac{1}{4^n}\binom{2r}{2n}\int_{0}^{1}u^{r-n-1/2}(1-u)^{2n}\,du\\(\text{Beta function})\qquad&=&\frac{\Gamma(2r+1)\Gamma(r-n+1/2)}{4^n\Gamma(2n-2r+1)\Gamma(r+n+3/2)}\end{eqnarray*}$$
Legendre's duplication formula converts the last expression into the wanted one, proving the combinatorial identity $\sum_{k=0}^{n}(\ldots)=(\ldots)$ as a consequence.
An algorithmic way for tackling combinatorial identities involving the product of (not too many) binomial coefficients is given by the Wilf-Zeilberger method.
