Lagrange interpolation formula

Statement

Suppose $k$ is a field with at least $n+1$ elements. Suppose $x_{0},x_{1},\dots ,x_{n}$ are distinct elements of $k$. Suppose $(y_{0},y_{1},\dots ,y_{n})\in k^{n+1}$. Define the polynomial:

$f(x)=\sum _{i=0}^{n}y_{i}\prod _{j\neq i}{\frac {x-x_{i}}{x_{j}-x_{i}}}$.

Then, $f$ is the only polynomial satisfying these two conditions:

• The degree of $f$ is at most $n$.
• $f(x_{r})=y_{r},0\leq r\leq n$.

Facts used

1. Degree of polynomial over a field bounds the number of roots

Proof

Given: A field $k$ with at least $n+1$ elements. $x_{0},x_{1},\dots ,x_{n}$ are distinct elements of $k$. $(y_{0},y_{1},\dots ,y_{n})\in k^{n+1}$. Define:

$f(x)=\sum _{i=0}^{n}y_{i}\prod _{j\neq i}{\frac {x-x_{j}}{x_{i}-x_{j}}}$.

To prove: $f$ is the only polynomial satisfying these two conditions:

• The degree of $f$ is at most $n$.
• $f(x_{r})=y_{r},0\leq r\leq n$.

Proof:

1. The fact that the degree of $f$ is at most $n$ follows from the fact that $f$ is a sum of polynomials, each of which is a product of $n$ linear polynomials (multipled by some constant).
2. The fact that $f(x_{r})=y_{r}$ follows by just substituting $x=x_{i}$ in the expression. Notice that for $i\neq r$, the product is zero, since the factor for $j=r$ is zero. Thus, the only product that survives is the one for $i=r$, and in this case, the expression simplifies to $y_{i}$.
3. The fact that it is the unique polynomial follows from the fact that if $f_{1}$ is another polynomial of degree at most $n$ with $f_{1}(x_{i})=y_{i}$, the polynomial $f-f_{1}$ has each $x_{i}$ as a root. Hence, $f-f_{1}$ is a polynomial of degree at most $n$ with $n+1$ distinct roots. This is a contradiction to fact (1).