Divided difference table ($D_{i,k}=f[x_i,\dots ,x_{i+k}]$)

A divided difference table arranges divided differences by starting interpolation node $i$ and order $k$. Its base column is $D_{i,0}=f(x_i)$; every later entry uses two neighboring entries from the previous column:The denominator spans all $k+1$ interpolation nodes of that entry, even though the numerator uses adjacent table entries. The interpolation nodes must be distinct; they need not be equally spaced or sorted.^[ref]

Take the polynomial $f(x)=x^3-2x+1$ at the interpolation nodes $(-1,0,2,3)$, giving values $(2,1,5,22)$. Its divided difference table isThe first divided differences are $(1-2)/(0+1)=-1$, $(5-1)/(2-0)=2$, and $(22-5)/(3-2)=17$. The second divided differences use the wider spans: $(2+1)/(2+1)=1$ and $(17-2)/(3-0)=5$. The third divided difference is $(5-1)/(3+1)=1$. Reading the top row gives the Newton polynomial coefficients $(2,-1,1,1)$, rather than all the entries in any one column.

The resulting Newton polynomial grows through four partial interpolants:At $x=2$, $p_1(2)=-1$ misses $f(2)=5$ by $6$; the correction $(x+1)x$ supplies exactly $6$ there and vanishes at the earlier interpolation nodes $-1,0$. At $x=3$, $p_2(3)=10$ misses $f(3)=22$ by $12$; the correction $(x+1)x(x-2)$ supplies exactly $12$ there and vanishes at all three earlier interpolation nodes. Each added term therefore preserves the previous agreements while satisfying the next one.

For $n+1$ interpolation nodes, the triangle contains $n+(n-1)+\cdots +1=n(n+1)/2$ recurrence steps. Once the top row is known, nested evaluation of the Newton polynomial uses only $n$ multiplications and $n$ additions per argument. The triangle organizes the work; the factors explain why the construction works.