> [!NOTE] Theorem 3.3 (Lagrange Inteprolation Theorem). > Let $m \geq 0$. Let $x_j \in \mathbb{R}, j \in$ $\{0, \ldots m\}$ be distinct real numbers, and $y_j \in \mathbb{R}, j \in\{0, \ldots m\}$ be any real numbers (not necessarily distinct). Then, there exists a unique $p_m(x) \in \mathscr{P}_m$ such that $p_m\left(x_j\right)=y_j \quad \forall j \in\{0, \ldots, m\}$ > ###### Proof First we prove that there exists polynomials $L_k \in \mathscr{P}_m$ such that $ L_k\left(x_j\right)= \begin{cases}1 & j=k \\ 0 & j \neq k\end{cases} $ Moreover, the polynomial $ p_m(x)=\sum_{k=0}^m L_k(x) y_k $ is also in $\mathscr{P}_m$ and satisfies $p_m\left(x_j\right)=y_j$ for $0 \leq j \leq m$. By assumption, if $L_k$ exists, then it is a polynomial of degree $m$ with roots at $x_j$ for $j \neq k$. Hence, $ L_k(x)=C_k \prod_{i \neq k}^m\left(x-x_j\right)=C_k\left(x-x_0\right) \cdots\left(x-x_{k-1}\right)\left(x-x_{k+1}\right) \cdots\left(x-x_m\right) $ for a constant $C_k \in \mathrm{R}$. To determine $C_k$, set $x=x_k$. Then $L_k\left(x_k\right)=1=$ $C_k \prod_{j \neq k}\left(x_k-x_j\right)$ and thus $ C_k=\frac{1}{\prod_{j \neq k}\left(x_k-x_j\right)} $ Since we assumed the $x_j$ to be distinct, we have never divided by zero. Consequently, we have shown the existence of $L_k$ by explicitly constructing it as $ L_k(x)=\prod_{j, k}^m \frac{x-x_i}{x_k-x_j} $ Next, set $ p_m(x):=\sum_{k=0}^m y_k L_k(x) $ Then $p_m\left(x_j\right)=\sum_{k=0}^m y_k L_k\left(x_j\right)=y_j L_j\left(x_j\right)=y_j$. Since $p_m(x)$ is a linear combination of various $L_k(x)$, it too is an element of $\mathscr{P}_m$. The case $m=0$ is clear. Assume $m \geq 1$. In lemma 3.2 we constructed a polynomial $p_m(x)$ of degree at most $m$ satisfying the condition (3.3), showing existence of the polynomial. For uniqueness, assume that we have two such polynomials $p_m(x), q_m(x) \in \mathscr{P}_m$ both satisfying the interpolation property (3.3). The goal is to show that they are identical. By assumption, the difference $p_m(x)-q_m(x)$ is also in $\mathscr{P}_m$, which must vanish at all nodes, i.e. $ p_m\left(x_j\right)-q_m\left(x_j\right)=y_j-y_j=0 \quad \forall j \in\{0, \ldots, m\} $ which is to say at $m+1$ distinct points. By the fundamental theorem of algebra, a non-zero polynomial of degree $m$ can have no more than $m$ distinct roots, from which it follows that $p_m(x)-q_m(x) \equiv 0$ or in other words $ p_m(x)=q_m(x) $ which completes the proof.