[proofplan] We prove the Newton interpolation formula by induction on $n$. The base case $n = 0$ is the constant polynomial $f[x_0]$. For the inductive step, the degree-$(n-1)$ interpolant $q$ at $x_0, \dots, x_{n-1}$ (given by the inductive hypothesis in Newton form) is extended to a degree-$n$ interpolant by adding a correction term $c\prod_{i=0}^{n-1}(x - x_i)$. The coefficient $c$ is determined by the interpolation condition at $x_n$ and equals $f[x_0, \dots, x_n]$ by uniqueness of the interpolating polynomial ([Existence and Uniqueness](/theorems/473)). [/proofplan] [step:Verify the base case $n = 0$] For $n = 0$: $p(x) = f[x_0] = f(x_0)$, which is the constant polynomial interpolating $f$ at $x_0$. [/step] [step:Extend the degree-$(n-1)$ interpolant to degree $n$] Assume the result holds for $n-1$ points. Let $q \in P_{n-1}[x]$ be the polynomial interpolating $f$ at $x_0, \dots, x_{n-1}$, which by the inductive hypothesis has the Newton form \begin{align*} q(x) &= f[x_0] + \sum_{k=1}^{n-1} f[x_0, \dots, x_k]\prod_{i=0}^{k-1}(x - x_i). \end{align*} Define \begin{align*} p(x) &= q(x) + c\prod_{i=0}^{n-1}(x - x_i), \end{align*} where $c$ is to be determined. Since $q(x_i) = f(x_i)$ for $i = 0, \dots, n-1$ and $\prod_{i=0}^{n-1}(x_j - x_i) = 0$ for each such $j$ (the product contains the factor $x_j - x_j = 0$), the polynomial $p$ interpolates $f$ at $x_0, \dots, x_{n-1}$ regardless of $c$. [/step] [step:Determine the coefficient $c$ and identify it as $f[x_0, \dots, x_n]$] The interpolation condition $p(x_n) = f(x_n)$ gives \begin{align*} c &= \frac{f(x_n) - q(x_n)}{\prod_{i=0}^{n-1}(x_n - x_i)}. \end{align*} By uniqueness of the interpolating polynomial ([Existence and Uniqueness](/theorems/473)), $p$ is the unique element of $P_n[x]$ interpolating $f$ at $x_0, \dots, x_n$. The leading coefficient of $p$ is $c$ (since $q$ has degree $\le n-1$ and $\prod_{i=0}^{n-1}(x - x_i)$ is monic of degree $n$). The leading coefficient of the degree-$n$ interpolant is $f[x_0, \dots, x_n]$ by the definition of divided differences (the $n$-th divided difference is the coefficient of $x^n$ in the interpolant). Therefore $c = f[x_0, \dots, x_n]$, completing the induction. [/step]