Uniqueness in Lagrange Interpolation Theorem? The polynomials $p(x) = 5x^3 - 27x^2 + 45x - 21$ and $q(x) = x^4 - 5x^3 + 8x^2 - 5x + 3$ both interpolate the points $(1,2) , (2,1) , (3,6), (4,47)$. Even though these polynomials are of different degree, I do not understand how this is possible when the Lagrange interpolation theorem states there is only one polynomial which should interpolate these points.
 A: There is a unique polynomial of degree $n$ or less through $n+1$ points but as many as you want of higher degree.
A: Working in the Newton basis makes this clearer. The Lagrange interpolation theorem says that your cubic polynomial is the unique polynomial interpolant whose degree is at most $3$. It can be written in the Newton basis as:
$$c_1 + c_2 (x-1) + c_3 (x-1)(x-2) + c_4 (x-1)(x-2)(x-3)$$
for some $c_1 , \dots , c_4$. If I now consider a polynomial of the form
$$c_1 + c_2 (x-1) + c_3 (x-1)(x-2) + c_4 (x-1)(x-2)(x-3) + c_5 (x-1)(x-2)(x-3)(x-4)$$
then no matter what $c_5$ is, this will also be an interpolant. (Why?) I can also replace $c_5$ by any polynomial I want, and it will still be an interpolant.
A: Hint $\,f(x)\,$ is a solution $\!\iff\! f(x) + (x\!-\!1)(x\!-\!2)(x\!-\!3)(x\!-\!4)g(x)\,$ is a solution, for any $\,g(x),\,$ since both take the same values for $\,x\in\{1,2,3,4\}.\,$ The least degree polynomial of RHS form is the remainder of $\,f(x)\,$ when divided by $\,h(x) = (x\!-\!1)\cdots(x\!-\!4).\,$ This is the unique solution having degree $\,< \deg h = 4,\,$ since the remainder $\,r(x)\,$ is unique $ $ (else $\ h\mid f-r, f-r',\,$ therefore $\,h\,$ divides their difference $\, r'-r,\,$ contra $\,\deg(r'-r) < \deg h,\,$ by $\,\deg r'<h,\ \deg r< h\,).$
If you know the Chinese Remainder Theorem (CRT) then you may find it instructive to reformulate Lagrange interpolation in the more general CRT form, by employing $\,f(x_i) = y_i \iff f\equiv y_i \pmod{ x - x_i}.$
