Given data points $\{(x_i,f(x_i)\}_{i=0}^{m}$, if we define divided difference recursively as:
$$f[x_0,\cdots,x_{k+1}] = \frac{f[x_1,\cdots,x_{k+1}]-f[x_0,\cdots,x_k]}{x_{k+1}-x_0} \text{ with the definition that} f[x_0] = f(x_0)$$
then it is true that the unique interpolating polynomial $L_m(x)$ of degree $m$ such that $L_m(x_i) = f(x_i)$ for all $i = 0\cdots m$ is given by:
$$
L_m(x) = \sum_{k=0}^mf[x_0,\cdots,x_k]\omega_k(x), \text{ where } \omega_k(x) = \prod_{i=0}^{k-1}(x-x_i).
$$
The question asks to show this. That is, show the coefficients of the interpolating polynomial of degree $m$ in the basis $\{\omega_k\}_{k=0}^{m}$ is exactly $a_k = f[x_0,\cdots,x_k]$, the divided differences.
To tackle this problem, I've attempted to use induction. The base step is trivial as $a_0 = f(x_0)$, but I am stuck on the inductive step. I supposed the degree $m$ interpolating polynomial of some data $\{(x_i,f(x_i)\}_{i=0}^{m}$ is indeed given by:
$$
L_m(x) = \sum_{k=0}^mf[x_0,\cdots,x_k]\omega_k(x)
$$
and I want to argue that $L_{m+1}(x) = \sum_{k=0}^{m+1}f[x_0,\cdots,x_k]\omega_k(x)$ is the interpolating polynomial of degree $m+1$ interpolating $\{(x_i,f(x_i)\}_{i=0}^{m+1}$, with any additional point $(x_{m+1},f(x_{m+1}))$ added.
Clearly, $L_{m+1}(x)$ interpolates $\{(x_i,f(x_i)\}_{i=0}^{m}$ by definition of the $\omega_k$'s, but I am stuck at showing $L_{m+1}(x_{m+1}) = f(x_{m+1})$. Hints will be extremely appreciated!
Best Answer
This proof was more delicate than I expected. First observe that by an easy induction, for all $x_0,\ldots, x_m$ we have $$f[x_0,\ldots, x_m]=f[x_m,\ldots,x_0]\,. \quad \quad (1)$$ Recall $L_m$ is defined to be the degree $m$ polynomial interpolating $f$ at $x_0,\ldots,x_m$. Our goal is to verify by induction that $$L_m(x)+f[x_0,\ldots,x_{m+1}] \, \omega_{m+1}(x)=L_{m+1}(x) \, \quad \quad (2) $$ for all choices of $x,x_0,\ldots, x_m.$
Since both sides of (2) are degree $m+1$ polynomials and (2) is clear for $x=x_0,\ldots,x_m$, it suffices to verify it also holds for $x=x_{m+1}$. To this end, define $Q_k$ as the degree $k$ polynomial interpolating $f$ at $x_1,\ldots,x_{k+1}$ and denote $$\psi_m(x):=\prod_{j=1}^m (x-x_j)=\frac{\omega_{m+1}(x)}{x-x_0} \,. \quad \quad (3)$$
By the induction hypothesis, equation (2) holds for polynomials of lower degree, so $$Q_m(x)=Q_{m-1}(x)+f[x_1,\ldots,x_{m+1}] \psi_{m}(x) \, \quad \quad (4) $$ and by considering the points in the reverse order $x_m,\ldots,x_1,x_0$ $$L_m(x)=Q_{m-1}(x)+f[x_m,\ldots,x_0] \psi_{m}(x) \, \quad \quad (5) $$ Subtracting the last two equations and setting $x=x_{m+1}$ gives $$Q_m(x_{m+1})-L_m(x_{m+1})=\Bigl(f[x_1,\ldots, x_{m+1}]- f[x_m,\ldots,x_0] \Bigr)\psi_{m}(x_{m+1})\quad \quad \quad \quad \quad \; \; \; \;$$ $$=f[x_0,\ldots, x_{m+1}]\, \omega_{m+1}(x_{m+1}) \,, \quad \quad (6) $$ using equations (1) and (3) in the last step. Since $Q_{m}(x_{m+1})=f(x_{m+1})=L_{m+1}(x_{m+1})$, equation (6) gives (2) for $x=x_{m+1}$. This completes the induction step and the proof of (2).