# How is a degree-$d$ polynomial uniquely characterized by its values at $d+1$ distinct points?

A degree-$d$ polynomial is uniquely characterized by its values at any $d+1$ distinct points.

Could someone explain why the statement above is necessarily true?

-
Look up polynomial interpolation and the Vandermonde matrix. –  Guess who it is. May 12 '12 at 16:12
This is equivalent to saying that a degree-$d$ polynomial which is equal to zero at $d + 1$ distinct points is identically zero. To prove this you can use the factor theorem (if $p(a) = 0$ then $p(x) = (x - a) q(x)$ for some polynomial $q$). There's no need to use the Vandermonde matrix. –  Qiaochu Yuan May 12 '12 at 16:18
You can show it using linear algebra. The system $$\underbrace{V}_{(d+1)\times (d+1)}\overbrace{x}^{(d+1)\times 1} = \underbrace{b}_{(d+1)\times 1}$$ has a unique solution if $V$ has full rank. –  user2468 May 12 '12 at 16:19

If you write down a general polynomial of degree $d$, i.e. with $d+1$ coefficients $a_i$ and plug in your $d+1$ given points, you will get $d+1$ independent equations in $d+1$ variables.
Edit 1: Another, less constructive, proof is to assume there are two different polynomials $f$ and $g$ of degree $d$ which have the same value at $d+1$ points. Then their difference $f-g$ is a non zero polynomial of degree $\leq d$ with at least $d+1$ zeros. But if $x_0$ is a zero, then $(x-x_0)|(f-g)$. You can easily show that this is a contradiction.
Edit 2: Or you could prove it by induction. Assume you have a unique polynomial $f$ of degree $d-1$ which has the desired value at $d$ distinct points (the case d=1 is easy). For a polynomial $g$ of degree $d$ which has the requested value at all of you $d+1$ points you have $g-f$ is of degree $d$ and has $d$ given zeros. Therefore it has $d$ fixed linear factors and has only a degree of freedom in the scalar factor. This factor is then uniquely determined by the $(d+1)^{st}$ point.