1
$\begingroup$

I am studing numerical analysis and I'm reading In wikipidia about it. I want to understand the Expanded form - I tried to prove this($f[x_0,\ldots,x_n]=\ldots$) by induction and failed.

Any Ideas on how this can be proven ?

1 Answers 1

5

For $n=1$, we have $\frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0}=\frac{f(x_1)-f(x_0)}{x_1-x_0}=f[x_0,x_1].$ If the formula f[x_0,\ldots,x_n]=\sum_{j=0}^n\frac{f(x_j)}{q'(x_j)}, where $q(\xi)=\prod_{k=0}^n(\xi-x_k)$, then denoting $q_1(\xi)=\prod_{k=1}^{n+1}(\xi-x_k)$, $q_2(\xi)=\prod_{k=0}^n(\xi-x_k)$ and $Q(\xi)=\prod_{k=0}^{n+1}(\xi-x_k)$, we have \begin{align*} f[x_0,\ldots,x_{n+1}]&=\frac{f[x_1,\ldots,x_{n+1}]-f[x_0,\ldots,x_n]}{x_{n+1}-x_0}\\ &=\frac 1{x_{n+1}-x_0}\left(\sum_{j=0}^n\frac{f(x_{j+1})}{q_1'(x_{j+1})}-\sum_{j=0}^n\frac{f(x_j)}{q_2'(x_j)}\right)\\ &=\frac 1{x_{n+1}-x_0}\left(\sum_{k=1}^{n+1}\frac{f(x_k)}{q_1'(x_k)}-\sum_{k=0}^n\frac{f(x_k)}{q_2'(x_k)}\right)\\ &=\frac 1{x_{n+1}-x_0}\left(\frac{f(x_{n+1})}{q_1'(x_{n+1})}+\sum_{k=1}^nf(x_k)\left(\frac 1{q_1'(x_k)}-\frac 1{q_2'(x_k)}\right)-\frac{f(x_0)}{q_2'(x_0)}\right). \end{align*} We have (x_{n+1}-x_0)q_1'(x_{n+1})=(x_{n+1}-x_0)\prod_{k=1}^n(x_{n+1}-x_k)=\prod_{k=1}^{n+1}(x_{n+1}-x_k)=Q'(x_{n+1}), (x_{n+1}-x_0)q_2'(x_0)=(x_{n+1}-x_0)\prod_{k=1}^n(x_0-x_k)=\prod_{k=1}^{n+1}(x_0-x_k)=Q'(x_0) and \begin{align*} \frac 1{q_1'(x_k)}-\frac 1{q_2'(x_k)}&=\prod_{j=1,j\neq k}^{n+1}\frac 1{x_k-x_j}-\prod_{j=0,j\neq k}^n\frac 1{x_k-x_j}\\ &=\prod_{j=0,j\neq k}^{n+1}\frac 1{x_k-x_j}(x_k-x_0-(x_k-(x_{n+1}))\\ &=(x_{n+1}-x_0)\prod_{j=0,j\neq k}^{n+1}\frac 1{x_k-x_j}, \end{align*} which gives f[x_0,\ldots,x_{n+1}]=\sum_{j=0}^{n+1}\frac{f(x_j)}{Q'(x_{j+1})}.