Proof of relation between divided difference and interpolation polynomial coefficient 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!
 A: 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).
A: Consider adding the table entries one by one...

*

*$p_0(x) = f_0$ interpolates the data on $x_0$.


*The interpolant on $x_0, x_1$ is given by
$$
p_1(x) = p_0(x) + c_1 (x-x_0).
$$
We can compute $c_1$ simply by prescribing   $p_1(x_1)= f_1$, which leads to
$$
p_0(x_1) + c_1(x_1-x_0)= f_1 \Leftrightarrow c_1 =\frac{f_1-f_0}{x_1-x_0} 
$$
hence,
$$
p_1(x) = f_0 + \frac{f_1-f_0}{x_1-x_0} (x-x_0)
$$


*The interpolant on $x_0, x_1, x_2$ is given by
$$
p_2(x)=p_1(x) + c_2 (x-x_0)(x-x_1)
$$
again, $c_2$ is computed by demanding $p_2(x_2)=f_2$:
$$
f_0+\frac{f_1-f_0}{x_1-x_0}(x_2-x_0) + c_2(x_2-x_0)(x_2-x_1) \Leftrightarrow c_2 = \cdots 
$$
This way, you recover the recursive definition of the divided differences, with the correspondence $c_k = f[x_0, \cdots, x_k]$. I think you can now reconstruct the inductive step.
