Given distinct $y_0,…,y_m$ in $\mathbb R$, let $N_m(x)$ be the Newton interpolation polynomial of degree $m$. That is, $N_m(x) = \sum_{n=0}^{m}a_nw_n(x)$ where $w_0 = 1$, $w_n(x) = (x-x_o)(x-x_1)…(x-x_{n-1})$ for $n > 0$ and the coefficients $a_n$ satisfies
$a_0 = y_0$
$a_0 + a_1w_1(x_1) = y_1$
…………………………………..
$a_0 + a_1w_1(x_m) + … + a_mw_m(x_m) = y_m$
Prove that $\displaystyle a_n = \sum_{j=0}^n\frac{y_j}{\prod_{k=0, k \neq j}^n(x_j – x_k)}$ for $0 \leq n \leq m$.
Hint is given in the book that $N_n(x) = L_n(x)$, for $0 \leq n \leq m$ where $L_n(x)$ is the Lagrange polynomial that interpolates through $y_o,…,y_m$. However this hint is not helping me much. Any further hints or solution is appreciated.
Best Answer
$$N_n(x) = \sum_{j=0}^n a_jw_j(x) = \sum_{j=0}^n a_j \prod_{k=0}^{j-1}(x-x_k) = \sum_{j=0}^n y_j \prod_{k=0, k\neq j}^n \frac{(x-x_k)}{(x_j-x_k)}$$ interpolates through the points $$(x_0,y_0), (x_1,y_1), \ldots, (x_{n-1},y_{n-1}), (x_n,y_n)$$ Note that the polynomial on the right side above is the Lagrange interpolation polynomial $L_n(x)$ suggested in the hint. Since $L_n(x)$ also interpolates through these $n+1$ points, it must be the same as $N_n(x)$. Note that $w_n(x)$ is the only polynomial of degree $n$ in the sum on the left while each polynomial in the sum on the right has degree $n$. Comparing the coefficients of $x^n$ on both sides, we get $$a_n = \sum_{j=0}^n \frac{y_j}{\prod_{k=0, k\neq j}^{n}(x_j-x_k)}.$$