Proof of Theorem 44 (Interpolation)

We will assume Theorem 43 and prove Theorem 44.

Let us first prove the existence of such a polynomial (later we will show that it is unique), given the points $(x_i, y_i)$ for all $i \in [d+1]$ where $x_i$ are distinct. Let us solve an easier problem first. When $y_2 = y_3 = \ldots = y_{d+1} = 0$, it is easy to construct such a polynomial $f$: We know that $x_2,\ldots, x_{d+1}$ should be the $d$ roots, so the polynomial should look something like (see a formal proof of this in Exercise 121),

$$f(x) = c(x-x_2)(x-x_3)\cdots (x- x_{d+1})$$

for some constant $c$, which is easy to figure out. By plugging in $y_1 = f(x_1) = c \cdot (\prod_{j=2}^{d+1} (x_1-x_j))$. This gives us the value of $c$ and therefore

$$f(x) = \frac{y_1 \cdot \prod_{j\neq 1} (x-x_j)}{\prod_{j\neq 1} (x_1 - x_j)}$$

Now, for all $i \in [d+1]$, we define the Lagrange basis function as

$$L_i(x) = \prod_{j: j \neq i}\frac{x-x_j}{x_i - x_j}$$

Exercise 120

Prove: $L_i(x_i) = 1$, and for all $j \neq i$, we have $L_i(x_j) = 0$.

Therefore, is simple to verify that

$$f(x) = \sum_{i \in [d+1]} y_i L_i(x)$$

is a degree-$d$ polynomial and satisfies $f(x_i) = y_i$ for all $i \in [d+1]$.

Next, we argue that such a polynomial is unique. Assume for the sake of contradiction that there exists another polynomial of degree $d$, called $g(x)$ such that $g(x_i) = y_i$ for all $i \in [d+1]$. Assume that $g$ and $f$ are different. Consider the polynomial $r(x) = g(x) - f(x)$. Notice that

$$(\forall i \in [d+1])\ r(x_i) = y_i - y_i = 0$$

This implies that polynomial $r$ (which has degree at most $d$) has $(d+1)$ distinct roots, a contradiction to Theorem 43.