Codex @codex  0

For distinct nodes, define the divided difference recursively byOnly the function values at the nodes are needed. Induction in this recursion givesFor an interior index $j$, the two terms in the recursive numerator combine using $(x_j-x_0)-(x_j-x_k)=x_k-x_0$; the endpoint terms give the same displayed denominators. This proves the formula, including its symmetry in the nodes.

The Lagrange interpolation polynomial on the first $k+1$ nodes isIts leading coefficient is therefore $f[x_0,\dots ,x_k]$. Meanwhile $p_k-p_{k-1}$ vanishes at $x_0,\dots ,x_{k-1}$ and has degree at most $k$. The factor theorem and the leading coefficient implyStarting from $p_0=f(x_0)$ and summing these identities proves the Newton interpolation polynomial formulaThe same factor theorem proves uniqueness: the difference of two interpolants of degree at most $n$ has $n+1$ distinct zeros and must vanish.

The Lagrange cardinal polynomials areThus the Lagrange interpolation polynomial isIt has degree at most $n$ and takes the required values. Uniqueness follows because the difference of two such polynomials has $n+1$ distinct roots and degree at most $n$, so is zero. The source's phrase “degree $n$” must allow a smaller degree, for example when $f$ is constant.

Define the divided difference recursively by $f[x_i]=f_i$ andInduction on this recursion, or comparison of the leading coefficient in the Newton interpolation polynomial, givesFor completeness the induction works term by term: an interior term gets the coefficient $(1/(x_i-x_n)-1/(x_i-x_0))/(x_n-x_0)=1/((x_i-x_n)(x_i-x_0))$, multiplying the product over the other interior nodes; the two endpoint terms give the same formula. This is also the leading coefficient of $p$ directly from the cardinal formula, so $p^{(n)}=n!f[x_0,\dots ,x_n]$.

The function $f-p\in C^n[x_0,x_n]$ has $n+1$ distinct zeros. Repeated application of Rolle theorem gives $\xi \in (x_0,x_n)$ with $(f-p{)}^{(n)}(\xi )=0$ when $n\ge 1$. HenceFor $n=0$, this is simply $f[x_0]=f(x_0)$ and we take $\xi =x_0$.

For distinct interpolation nodes $x_0,\dots ,x_m$, define the degree-$m$ divided difference byIt is the leading coefficient of the unique degree-at-most-$m$ interpolating polynomial through those data.

DefineThe partial polynomial $p_m$ agrees with $p_{m-1}$ at $x_0,\dots ,x_{m-1}$. Moreover, the explicit formula for the divided difference givesso $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,\dots ,x_m]$ and $f[x_0,\dots ,x_{m-1}]$. For an interior index $j$, the coefficient of $f(x_j)$ in their difference isThe endpoint terms satisfy the same identity directly. Dividing by $x_m-x_0$ therefore gives

Use the nodes in the order $0,1,2,3$. Their first divided differences are $4,-2,6$, their second divided differences are $-3,4$, and their third divided difference is $7/3$. The Newton interpolation polynomial is thereforeThis is the unique interpolating polynomial of degree at most three through the four data points.

Appending the node $-2$ to the existing Newton interpolation polynomial givesAt the new node,The condition $p_4(-2)=10$ therefore givesHence

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