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\ne 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\le r\le 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\ne 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\le r\le 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\ne 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).