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!

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.
