Past exam of the mathematics course of the University of Cambridge / 2002 / ib / Paper 2 / 14B (Numerical Analysis)

For distinct interpolation nodes $x_0,\dots ,x_n$, let $p_n$ be the unique polynomial of degree at most $n$ satisfying $p_n(x_i)=f(x_i)$. Existence follows from the Lagrange polynomial expressionuniqueness follows because the difference of two interpolants has $n+1$ distinct zeros but degree at most $n$.

Define the divided difference $f[x_0,\dots ,x_n]$ to be the coefficient of $x^n$ in $p_n$, even when that coefficient is zero. For $n=0$ this gives $f[x_0]=f(x_0)$. Permuting the nodes does not change the interpolation conditions, so it does not change their unique interpolant or this coefficient. The divided difference is symmetric in all the nodes. Equivalently its symmetric expression is

For $n\ge 1$, let $p_L,p_R$ be the interpolation polynomials of degree at most $n-1$ on nodes $x_0,\dots ,x_{n-1}$ and $x_1,\dots ,x_n$, respectively. The polynomialhas degree at most $n$. At $x_0$ it equals $p_L(x_0)$; at $x_n$ it equals $p_R(x_n)$. At each common node both interpolants equal $f$, and the displayed weights sum to one, so $p$ also equals $f$ there. Thus it is the full interpolant by uniqueness.

Its coefficient of $x^n$ is the difference of the leading coefficients of $p_R,p_L$ divided by $x_n-x_0$. By the definition of a divided difference,

Write $D=f[x_0,\dots ,x_n]$ and let $D_i$ be the divided difference with $x_i$ omitted. By symmetry from part (a), reorder the full list so that its first node is $x_i$ and its last is $x_j$. The recurrence from part (b) then has first omitted-node term $D_i$ and second omitted-node term $D_j$, and givesThis proves the requested identity for every pair $i\ne j$ and fixes its sign explicitly; it is one of the omitted-node identities for divided differences.

Continue with $D,D_i$ from part (c). Comparing omission of $x_i$ and $x_n$ givesComparing omission of $x_0$ and $x_n$ gives $D_0=D_n+(x_n-x_0)D$. Eliminating $D$ provesHere $D_n=f[x_0,\dots ,x_{n-1}]$ and $D_0=f[x_1,\dots ,x_n]$, so this is exactly the required omitted-node identities for divided differences. The original nodes need not be ordered, and the formula remains valid even if $\gamma$ lies outside $[0,1]$.