 Solution

For distinct nodes, define the divided difference byThis is the coefficient of $x^k$ in the Lagrange interpolation polynomial through the first $k+1$ data points.

Let $p_k$ denote that interpolating polynomial. The difference $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$, soThe Lagrange formula shows that the leading coefficient of $p_k$ is $f[x_0,\dots ,x_k]$, whereas $p_{k-1}$ has degree at most $k-1$. Hence $c_k=f[x_0,\dots ,x_k]$. Starting with $p_0=f(x_0)$ and iterating gives the Newton interpolation polynomial

The divided-difference recurrence isFor three nodes, the triangular table iswhere each entry in a new column uses the two adjacent entries to its left. There are $n$ first differences, $n-1$ second differences, and so on, each requiring one division. The exact total is