Legendre polynomial property How do  i show from the Legendre's Polynomial equation $$P_n(x)=\sum_{k=0}^N \dfrac{(-1)^k(2n-2k)!}{2^nk!(n-k)!(n-2k)!}x^{n-2k}$$ where $N=n/2$ for even $n$ and $ N=(n-1)/2$ for odd $n$. Using just this information how to show $P_n(1)=1$?
Can somebody hint?
 A: Suppose we seek to prove that
$$\sum_{k=0}^n {n\choose k} (-1)^k {2n-2k\choose n} = 2^n.$$
The LHS is
$$[z^n] (1+z)^{2n} \sum_{k=0}^n {n\choose k} (-1)^k
\frac{1}{(1+z)^{2k}}
\\ = [z^n] (1+z)^{2n}
\left[ 1-\frac{1}{(1+z)^2} \right]^{n}
\\ = [z^n] (z^2+2z)^n = [z^n] z^n (z+2)^n
= [z^0] (z+2)^n = 2^n.$$
The binomial coefficient ${2n-2k\choose n} = [z^n] (1+z)^{2n-2k}$ takes care of the upper range as given by OP because with $k\le n$ it yields zero when $n\gt 2n-2k$ or $2k\gt n.$
A: Notice that you can write this then as
$$2^n=\sum _{k=0}^n(-1)^k\binom{n}{k}\binom{2(n-k)}{n}=\sum _{k=0}^n(-1)^k\binom{n}{k}\binom{2(n-k)}{n-2k}.$$
In how many ways can you choose $n$ numbers out of $2n$ in such a way that you do not pick $i$ and $i+n$ for any $1\leq i\leq n$? 
Well, you can see that this can be done in $2^n$ ways by either choosing from the first $n$ numbers or the latest $n$ numbers or you can do this by doing all ways, i.e. $\binom{2n}{n}$, minus picking at least one of these pairs. Call $A_i=\{\text{pick }i,i+n\text{ to be chosen}\}$, see for example that $|A_i|=\binom{2(n-1)}{n-2}$. Then, by double counting, you have that
$$2^n=\binom{2n}{n}-\left | \bigcup _{i=1}^nA_i\right |.$$
Inclusion-exclusion on this equality gives you the result.
