explicit formula for divided differences

Theorem 1.

The $n$-th divided difference of a function $f$ can be written explicitly as

$${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\dots },x_n]=\sum _{i=0}^n\frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n}{j\ne i}}(x_i-x_j)}$$

Proof.

We will proceed by recursion on $n$. When $n=1$, the formula to be provenreduces to

$${\mathrm{\Delta }}^{1}f[x_0,x_1]=\frac{f(x_0)}{x_0-x_1}+\frac{f(x_1)}{x_1-x_0},$$

which agrees with the definition of ${\mathrm{\Delta }}^{1}f$.

To prove that this is correct when $n>1$, one needs to check that it the recurrence relation for divided differences.

${\displaystyle \sum _{\genfrac{}{}{0pt}{}{0\le i\le n+1}{i\ne 0}}}{\displaystyle \frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 0}}}(x_i-x_j)}}$$-{\displaystyle \sum _{\genfrac{}{}{0pt}{}{0\le i\le n+1}{i\ne 1}}}{\displaystyle \frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 1}}}(x_i-x_j)}}$

$={\displaystyle \frac{f(x_1)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 0}}}(x_1-x_j)}}-{\displaystyle \frac{f(x_0)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 1}}}(x_0-x_j)}}+$

$\mathrm{\hspace{1em}\hspace{1em}}{\displaystyle \sum _{2\le i\le n+1}}f(x_i)\left({\displaystyle \frac{1}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 0}}}(x_i-x_j)}}-{\displaystyle \frac{1}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{\genfrac{}{}{0pt}{}{j\ne i}{j\ne 1}}}(x_i-x_j)}}\right)$

$=-{\displaystyle \frac{(x_0-x_1)f(x_0)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_0-x_j)}}+{\displaystyle \frac{(x_1-x_0)f(x_1)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_1-x_j)}}+$

$\mathrm{\hspace{1em}\hspace{1em}}{\displaystyle \sum _{2\le i\le n+1}}f(x_i)\left({\displaystyle \frac{x_i-x_0}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_i-x_j)}}-{\displaystyle \frac{x_i-x_1}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_i-x_j)}}\right)$

$={\displaystyle \frac{(x_1-x_0)f(x_0)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_0-x_j)}}+{\displaystyle \frac{(x_1-x_0)f(x_1)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_1-x_j)}}+(x_1-x_0){\displaystyle \sum _{2\le i\le n+1}}{\displaystyle \frac{(x_1-x_0)f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_i-x_j)}}$

$=(x_1-x_0){\displaystyle \sum _{0\le i\le n+1}}{\displaystyle \frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_i-x_j)}}$

Thus, we see that, if

$${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\dots },x_n]=\sum _{i=0}^n\frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n}{j\ne i}}(x_i-x_j)},$$

then

$${\mathrm{\Delta }}^{n+1}f[x_0,\mathrm{\dots },x_{n+1}]=\sum _{i=0}^{n+1}\frac{f(x_i)}{\prod _{\genfrac{}{}{0pt}{}{0\le j\le n+1}{j\ne i}}(x_i-x_j)}.$$

Hence, by induction, the formula holds for all $n$.∎

This formula may be phrased another way by introducing the polynomials $p_n$ defined as

$$p_n(x)=\prod _{i=0}^n(x-x_i).$$

We may write

$${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\dots },x_n]=\sum _{i=0}^n\frac{f(x_i)}{p^{\prime }(x_i)}.$$

Either form of the explicit formula makes it obvious that divided differencesare symmetric functions of $x_0,x_1,\mathrm{\dots }$.