# 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.

• You seem to be looking for interpolating polynomials. See this: en.wikipedia.org/wiki/… Jun 17, 2014 at 23:40
• There is a unique polynomial of degree $\le n$ through $n+1$ points $(x_i,y_i)$, where the $x_i$ are distinct. The polynomial need not have degree exactly $n$. Jun 18, 2014 at 4:00
• @AndréNicolas Not true. Given the points $(0,0)$, $(1,1)$, and $(2,3)$, there does not exist a 1st degree polynomial (a line) that goes through all 3 points. Did you mean "$\ge$"? Jun 18, 2014 at 4:46
• Any arbitrary 3 points, then. Jun 18, 2014 at 4:49
• There is no quadratic (degree two) polynomial which passes through the points $(0,1)$, $(1,1)$, and $(2,1)$. There is however a constant function which does.
– user123641
Apr 18, 2015 at 17:01

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 equal to or smaller than $$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.

• I think it would be waaaaay simpler to just say there are n unknowns with n equations. People are much more likely to be familiar with this resulting in a unique answer than they are to know what a Vandermonde matrix is (even though saying n unknowns with n equations is a slight simplification since the equations must be linearly independent). Oct 12, 2017 at 3:54
• I think you forgot the equation for $(x_{n+1}, y_{n+1})$. Otherwise your Vandermonde matrix wouldn't even be quadratic ($n$ rows, $n+1$ columns) and you couldn't argue with the determinant Jun 16, 2021 at 15:00
• @Quotenbanane You are right. Thank you for pointing out my mistake.
– mfl
Jun 17, 2021 at 7:36
• @JosephGarvin The first half of the answer already clearly shows n unknowns with n equations. So, if you want to stop there, you can stop there. He's just noting that the difficulty of proving that those n equations have a solution, is equal to the difficulty in proving that a Vandermonde has non-zero determinant, because both are proving the exact same thing. (Such a proof isn't that hard though) Oct 31, 2021 at 16:48
• The polynomial $p_n(x)$ as stated " of degree n" is not correct. It's of a degree $\leq n.$ This might seem trivial but it's extremely important to not remember the interpolation problem (and solution) as: throught $n+1$ points there is unique polynomial of degree $n$-- this is not true. What's true is that through $n+1$ points there is unique polynomial of degree $\leq n.$ For example every polynomial $p$ of degree $\leq n$ conincides with it's Lagrange interpolating polynomial $L_n(p,x)$ of $n+1$ nodes. And the Lagrange polynomial of any function of $n+1$ nodes is of degree most $n.$ Jul 3 at 12:59

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$.

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...

• Just to make sure I am following, does the "two points" then mean we're approximating a 2 degree polynomial? thank you! Oct 3, 2021 at 8:50

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.