I want to find the expression for $P_n(x)$ with $x = 0$, ie $P_n(0)$ for any $n$. The first few non-zero legendre polynomials with $x=0$ are
$P_0(0) = 1$, $P_2(0) = -\frac{1}{2}$, $P_4(0) = \frac{3}{8}$, $P_6(0) = -\frac{5}{16}$, $P_8(0) = \frac{35}{128}$ but I can't find a relationship between them to write as an equation for arbitrary $n$. Any help is appreciated.
One way to define Legendre polynomials is through its generating function:
$$\frac{1}{\sqrt{1-2xt+t^2}} = \sum_{n=0}^\infty P_n(x)t^n$$ Together with following sort of well known expansion: $\displaystyle\;\frac{1}{\sqrt{1-4z}} = \sum_{k=0}^\infty \binom{2k}{k} z^k$, we have
$$\sum_{n=0}^\infty P_n(0) t^n = \frac{1}{\sqrt{1+t^2}} = \sum_{k=0}^\infty \binom{2k}{k}\left(-\frac{t^2}{4}\right)^k \quad\implies\quad P_n(0) = \begin{cases} \frac{(-1)^k}{4^k} \binom{2k}{k}, & n = 2k\\ 0, & \text{ otherwise } \end{cases}$$
If you look here, the recurrence relation is $$(n+1) P_{n+1}(x) = (2n+1) x P_n(x) - n P_{n-1}(x)$$ So $$(n+1) P_{n+1}(0) = - n P_{n-1}(0)$$ In the same Wikipedia page, you will find that, from Bonnet recursion formula,
$$P_n(x) = \sum_{k=0}^n (-1)^k \begin{pmatrix} n \\ k \end{pmatrix}^2 \left( \frac{1+x}{2} \right)^{n-k} \left( \frac{1-x}{2} \right)^k$$ So the result as given in achille hui's answer.
See Proving a property of Legendre Polynomials where the following formula is proven:
\begin{equation} \begin{split} P_{2n}(0) &=\frac{1}{2^{2n}}\sum_{k=0}^{2n}\binom{2n}{k}^2(-1)^k = \frac{1}{2^{2n}}\binom{2n}{n}(-1)^n = \frac{(-1)^n(2n)!}{2^{2n}n!^2} \end{split} \end{equation}
