Legendre polynomial property

Question

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?

Answer 1

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.$

Answer 2

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.