I am struggling with this problem on my numerical analysis homework. We're talking about polynomial interpolation and we just learned about divided differences like two days ago.
"Show that the following explicit formula is valid for divided differences:"
$$f\left[x_{0}, x_{1}, \ldots, x_{n}\right]=\sum_{i=0}^{n} f\left(x_{i}\right) \prod_{j \neq i, j=0}^{n}\left(x_{i}-x_{j}\right)^{-1}$$
HINT: If two polynomials are equal, the coefficients of $x^n$ in each are equal.
I get divided differences, and how they are defined recursively. I am also very familiar with both the Lagrange and Newton forms of the unique interpolation polynomial. But I just can't figure out where to begin here. The hint doesn't help me either. Any help is greatly appreciated.
Best Answer
The interpolating polynomial can be given by both these formulas: $$ p_n(x)= \sum_{i=0}^n f(x_i) \prod_{j\ne i}\frac{x-x_j}{x_i-x_j} $$
$$ p_n(x)=\sum_{i=0}^n f[x_0,\cdots, x_i] \prod_{j=0}^{i-1}(x-x_i)$$
The coefficients of $x^n$ in the second expression is $f[x_0, \cdots , x_n]$, and the same coefficient in the first expression is $\sum_{i=0}^n f(x_i) \prod_{j\ne i} \frac{1}{x_i-x_j}$. The uniqueness of the interpolating polynomial forces these coefficients to be the same.