Degree of polynomial interpolating the primes

The degree of $p_n(x)$ is always $n-1$. The proof is by induction.

Note that $p_1(x) = 2$ has degree $0$. Now assume that $p_{n}(x)$ has degree $n-1$. We want to prove that $p_{n+1}(x)$ has degree $n$. Assume otherwise, so $p_{n+1}(x)$ also had degree at most $n-1$. Then since $p_{n+1}(x)$ and $p_n(x)$ agree on the first $n$ values, it must be the case that $p_{n+1}(x) = p_n(x)$. In particular, to obtain a contradiction, it suffices to show that

$$p_n(n+1) \ne^{?} p_{n+1}.$$

In fact, we simply will prove that $p_n(n+1)$ is always even which does the job.

We can write down a formula for $p_n(x)$, namely

$$p_n(x) = \sum_{i=1}^{n} p_i \cdot \frac{(x-1)(x-2) \ldots \widehat{(x-i)} \ldots (x - n)}{(i-1)(i-2) \ldots \widehat{(i-i)} \ldots (i - n)},$$

where the hat indicates the term is omitted. This is clearly a polynomial of degree at most $n-1$ and $p_n(i) = p_i$. (This is the general formula for Lagrange interpolation specialized to this case.)

Hence

$$\begin{aligned} p_n(n+1) = & \ \sum_{i=1}^{n} p_i \cdot\frac{ n!/(n+1-i)}{(i-1)! (n-i)! (-1)^{n-i}}\\ = & \ (-1)^{n-1} \sum_{i=1}^{n} p_i \cdot \frac{ n!}{(i-1)! (n+1-i)!} (-1)^{i-1} \\ = & \ (-1)^{n-1} \sum_{i=1}^{n} p_i \cdot \binom{n}{i-1} (-1)^{i-1}\\ = & \ (-1)^{n-1} \sum_{i=0}^{n-1} p_{i+1} \binom{n}{i} (-1)^i\end{aligned}$$

Now we use the fact that, with the exception of $p_1 = 2$, the primes are all odd. It follows that

$$p_{n}(n+1) \equiv \sum_{i=1}^{n-1} (-1)^i \binom{n}{i} \mod 2.$$

But now

$$\sum_{i=1}^{n-1} (-1)^i \binom{n}{i} = (1-1)^n - 1 - (-1)^n \equiv 0 \mod 2,$$

is even for $n > 0$, and hence $p_{n}(n+1)$ is even, and thus $\ne p_{n+1}$, as desired.