Prove there exists a unique $n$-th degree polynomial that passes through $n+1$ points in the plane I know given two points in the plane $(x_1,y_1)$ and $(x_2,y_2)$ there exists a unique 1st degree (linear) polynomial that passes through those points. We all learned in Algebra how to find the slope between those points and then calculate the y-intercept.
To take it down a notch, given the point $(a,b)$, the unique 0th degree polynomial that passes through it is $y=b$.
My conjecture is that given three points $(x_1,y_1)$, $(x_2,y_2)$, and $(x_3,y_3)$, there exists a 2nd degree (quadratic) polynomial that passes through these points, and furthermore, that polynomial is unique. I wonder, how would one determine the equation of this quadratic?
If my conjecture is correct, a corollary would be the generalization that given any $\left(n+1\right)$ points in the plane, there exists one unique $n$th degree polynomial that passes through those points.
Please prove, or disprove with a counter-example.
Further Readings:


*

*658789 is a related question but I'm not sure if it's exactly what I'm looking for.

*This very cool interactive web app lets you drag points around and shows the polynomial that goes through them

 A: johannesvalks' answer proves existence but not uniqueness.  The Lagrange interpolation polynomials used will have degree $\le n$, as each is the sum of polynomials. Given two polynomials $P,Q$ with $\deg(P),\deg(Q)\le n$ both passing through $n+1$ distinct points $(x_i,y_i)$ with $1\le i\le n+1$, divide to get $P=(x-x_i)P_i+y_i$ and $Q=(x-x_i)Q_i+y_i$, for some $P_i,Q_i$, so that $$P-Q=(x-x_i)(P_i-Q_i).$$  Then $P-Q$ has $n+1$ distinct roots, while $P$ and $Q$ have at most $n$, so $P-Q$ must be the zero polynomial.
A: Assume you have given $n+1$ points $(x_1,y_1),\cdots, (x_{n+1},y_{n+1}).$ (Of course, $x_i\ne x_j$ if $i\ne j.$) A polynomial of degree $n$ is of the form $p_n(x)=a_nx^n+\cdots+a_1x+a_0.$ To study the existence and uniqueness of such a polynomial consider the system of linear equations:
$$
\left\{\begin{array}{ccc}
a_nx_1^n+a_{n-1}x_1^{n-1}\cdots+a_1x_1+a_0 & =& y_1\\ \vdots & &\\
a_nx_{n+1}^n+a_{n-1}x_{n+1}^{n-1}\cdots+a_1x_{n+1}+a_0 & =& y_{n+1}
\end{array}\right.
$$
We write the system as
$$
\begin{pmatrix}x_1^n & x_1^{n-1} &\cdots & x_1 & 1 \\ \vdots & \vdots & \ddots & \vdots \\ x_{n+1}^n &  x_{n+1}^{n-1}& \cdots & x_{n+1} & 1\end{pmatrix} \begin{pmatrix} a_n \\ \vdots \\ a_0 \end{pmatrix}=\begin{pmatrix} y_1 \\ \vdots \\ y_{n+1} \end{pmatrix}
$$
Since the matrix of coefficients of the system is non singular (it is a Vandermonde matrix (see Vandermonde)) the system has a unique solution, that is, there exists one polynomial of degree $n$ through the $n+1$ given points, and it is unique.
A: For an easy proof of uniqueness of such a polynomial (johannesvalks gives existence) assume we have $f,g$ of degree $n$ with $f(x_i)=g(x_i)=y_i$ for $1\leq i \leq n+1$.
Then $f-g$ has degree no bigger than $n$, so if $f-g\ne 0$ then $f-g$ has at most $n$ roots, but $f-g$ has at least $n+1$ roots so $f=g$.
A: You can define
$$ P_k(x) = \prod_{\jmath \ne k}^n \frac{ x - x_\jmath }{ x_k - x_\jmath } $$
It is clear that
$$ P_k(x_\ell) = \delta_{k\ell} $$
Then you can define
$$ f(x) = \sum_{k=1}^n y_k P_k(x) $$
and you will find
$$ f(x_\ell) = \sum_{k=1}^n y_k \delta_{k\ell} = y_l$$
The function $f(x)$ is a polynomial of degree $n-1$
So in general, such a polynomial is given by
$$ f(x) = \sum_{k=1}^n y_k \prod_{\ell \ne k}^n \frac{ x - x_\ell }{ x_k - x_\ell} $$

Two points gives
$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} + y_2 \frac{x-x_1}{x_2-x_1} $$
Three points gives
$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} \frac{x-x_3}{x_1-x_3} + y_2 \frac{x-x_1}{x_2-x_1} \frac{x-x_3}{x_2-x_3} + y_3 \frac{x-x_1}{x_3-x_1} \frac{x-x_2}{x_3-x_2} $$
Four points gives
$$ f(x) = y_1 \frac{x-x_2}{x_1-x_2} \frac{x-x_3}{x_1-x_3} \frac{x-x_4}{x_1-x_4}
+ y_2 \frac{x-x_1}{x_2-x_1} \frac{x-x_3}{x_2-x_3} \frac{x-x_4}{x_2-x_4}\\
+ y_3 \frac{x-x_1}{x_3-x_1} \frac{x-x_2}{x_3-x_2} \frac{x-x_4}{x_3-x_4}
+ y_4 \frac{x-x_1}{x_4-x_1} \frac{x-x_2}{x_4-x_2} \frac{x-x_3}{x_4-x_3}$$
and so on...
