Degree of polynomial interpolating the primes The polynomial $p_3(x)$ passes through the points
$(1,2), (2,3), (3,5)$, where $2,3,5$ are the first three primes:
$$
p_3(x) = \frac{x^2}{2}-\frac{x}{2}+2 \;.
$$
Similarly, one can form an interpolating polynomial $p_n(x)$ that
passes through the first $n$ primes.
For example:
$$
p_5(x) = \frac{x^4}{8}-\frac{17
   x^3}{12}+\frac{47
   x^2}{8}-\frac{103 x}{12}+6 \;.
$$
One can check that 
\begin{eqnarray}
p_5(1) &=& 2 \\
p_5(2) &=& 3 \\
p_5(3) &=& 5 \\
p_5(4) &=& 7 \\
p_5(5) &=& 11 \;.
\end{eqnarray}
My question is:

Q. Is the degree of $p_n(x)$ ever strictly less than $n{-}1$, for any $n$?

The answer to Q is positive if a "coincidence" occurs,
such that a smaller degree
polynomial captures those $n$ prime points.
Do such coincidences ever occur?
 A: 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.
A: Not really an answer, but consider a more general question:

Does the polynomial interpolating $n$ consecutive primes $p_{m+1},\dots,p_{m+n}$ always have maximum degree $n-1$?

The answer is a strong no because $3,5,7$ and $251,257,263,269$ are consecutive primes in arithmetic progression.
Small examples are known for $3 \le n \le 6$. See Wikipedia.
The polynomial interpolating the four consecutive primes $17, 19, 23, 29$ has degree $2$, not $3$. So does the polynomial interpolating the four consecutive primes $p_{m+1},\dots,p_{m+4}$ for $m \in \{6,10,12,17,21,48,57,68,69,74,84,90,103,110,115,121,122,126,131,172,181\}$.
A: Yes. Given $n$ unique data points, there is a unique polynomial of degree $n-1$ that interpolates the data. This is one of the first results in the interpolation section of any numerical analysis/methods course. Using data points constructed with primes is a specific case of this. If you write out the interpolation conditions, you'll see that this is equivalent to solving an $n \times n$ linear system. 
