# Deriving Newton's divided differences from sub-interval interpolation

I am reading about Newton's divided differences and I am confused by the following derivation of the coefficients of the Newton's polynomial.

The Newton's polynomial is given as

$$P_n(x) = a_0 + a_1(x - x_0) + a_2(x-x_0)(x-x_1) + \dots + a_n(x-x_0)...(x-x_{n-1})$$ (1)

A polynomial of order $$n$$ can be constructed from two polynomials of order $$n-1$$ by dividing the support in two parts like this

$$P_{k,k+1,\dots,k+j}(x) = \dfrac{(x- x_k)P_{k+1,\dots,k+j}(x)-(x- x_{k+j})P_{k,\dots,k+j-1}(x)}{x_{k+j} - x_k}$$ (2)

This I understand.

The next statement is confusing me.

Because a polynomial of order $$n$$ is unique for a specific support, an immediate consequence of this is that the coefficients $$a_i$$ in (1) are Newton's divided differences, because $$a_j$$ is the highest coefficient of a polynomial $$P^*_{0,\dots,j}(x)$$ for the $$(j+1)$$ support points $$((x_0, y_0), \dots (x_j, y_j))$$.

This "immediate consequence" is not at all immediate to me. :)

I understand that the divided differences can be derived in different ways for the n-th coefficient, there are answers already available for this question, I don't see how the interpolation with sub-polynomials immediately leads to $$a_n = [y_0, \dots, y_n]$$.

## 1 Answer

The author of the text may well be able to reach the conclusion immediately. This is not necessarily true for a specific reader who may not have the necessary background or even for the intended audience (very bad scholarship on part of the author). However, writing simply about simple matters is frightfully hard and requires patience and practice.

My answer to the cited question only came to me, because I had occasion to study Neville's algorithm for evaluating the interpolating polynomial.

• Thanks, it was the wording that confused me, namely "directly follows". I will take a look at your answer of the other question to see how induction works in this case. – tmaric Jul 16 at 9:22