= Solution
For distinct <interpolation nodes> $x_0,\ldots,x_m$, define the degree-$m$ <divided difference> by
$$
f[x_0,\ldots,x_m]
=\sum_{j=0}^m\frac{f(x_j)}{\prod_{\substack{0\leq k\leq m\\k\ne j}}(x_j-x_k)}.
$$
It is the leading coefficient of the unique degree-at-most-$m$ <polynomial interpolation>[interpolating polynomial] through those data.
Define
$$
p_n(x)=f[x_0]+\sum_{m=1}^nf[x_0,\ldots,x_m]\prod_{i=0}^{m-1}(x-x_i).
$$
The partial polynomial $p_m$ agrees with $p_{m-1}$ at $x_0,\ldots,x_{m-1}$. Moreover, the explicit formula for the divided difference gives
$$
f[x_0,\ldots,x_m]
=\frac{f(x_m)-p_{m-1}(x_m)}{\prod_{i=0}^{m-1}(x_m-x_i)},
$$
so $p_m(x_m)=f(x_m)$. Induction shows that $p_n(x_j)=f(x_j)$ for every $j$. By uniqueness of <polynomial interpolation>, this is the required <Newton interpolation polynomial>.
For the recursion, substitute the explicit formulas for $f[x_1,\ldots,x_m]$ and $f[x_0,\ldots,x_{m-1}]$. For an interior index $j$, the coefficient of $f(x_j)$ in their difference is
$$
\frac1{(x_j-x_m)\prod_{\substack{1\leq k\leq m-1\\k\ne j}}(x_j-x_k)}
-\frac1{(x_j-x_0)\prod_{\substack{1\leq k\leq m-1\\k\ne j}}(x_j-x_k)}
=\frac{x_m-x_0}{\prod_{\substack{0\leq k\leq m\\k\ne j}}(x_j-x_k)}.
$$
The endpoint terms satisfy the same identity directly. Dividing by $x_m-x_0$ therefore gives
$$
\boxed{f[x_0,\ldots,x_m]
=\frac{f[x_1,\ldots,x_m]-f[x_0,\ldots,x_{m-1}]}{x_m-x_0}}.
$$
Back to article page
