# explicit formula for divided differences

###### Theorem 1.

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

 $\Delta^{n}f[x_{0},\ldots,x_{n}]=\sum_{i=0}^{n}{f(x_{i})\over\prod\limits_{0% \leq j\leq n\atop j\neq i}(x_{i}-x_{j})}$
###### Proof.

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

 $\Delta^{1}f[x_{0},x_{1}]={f(x_{0})\over x_{0}-x_{1}}+{f(x_{1})\over x_{1}-x_{0% }},$

which agrees with the definition of $\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_{0\leq i\leq n+1\atop i\neq 0}{f(x_{i})\over\prod\limits_{0% \leq j\leq n+1\atop{j\neq i\atop j\neq 0}}(x_{i}-x_{j})}$ $\displaystyle-\sum_{0\leq i\leq n+1\atop i\neq 1}{f(x_{i})\over\prod\limits_{0% \leq j\leq n+1\atop{j\neq i\atop j\neq 1}}(x_{i}-x_{j})}$ $\displaystyle={f(x_{1})\over\prod\limits_{0\leq j\leq n+1\atop{j\neq i\atop j% \neq 0}}(x_{1}-x_{j})}-{f(x_{0})\over\prod\limits_{0\leq j\leq n+1\atop{j\neq i% \atop j\neq 1}}(x_{0}-x_{j})}+$ $\displaystyle\qquad\sum_{2\leq i\leq n+1}f(x_{i})\left({1\over\prod\limits_{0% \leq j\leq n+1\atop{j\neq i\atop j\neq 0}}(x_{i}-x_{j})}-{1\over\prod\limits_{% 0\leq j\leq n+1\atop{j\neq i\atop j\neq 1}}(x_{i}-x_{j})}\right)$ $\displaystyle=-{(x_{0}-x_{1})f(x_{0})\over\prod\limits_{0\leq j\leq n+1\atop j% \neq i}(x_{0}-x_{j})}+{(x_{1}-x_{0})f(x_{1})\over\prod\limits_{0\leq j\leq n+1% \atop j\neq i}(x_{1}-x_{j})}+$ $\displaystyle\qquad\sum_{2\leq i\leq n+1}f(x_{i})\left({x_{i}-x_{0}\over\prod% \limits_{0\leq j\leq n+1\atop j\neq i}(x_{i}-x_{j})}-{x_{i}-x_{1}\over\prod% \limits_{0\leq j\leq n+1\atop j\neq i}(x_{i}-x_{j})}\right)$ $\displaystyle={(x_{1}-x_{0})f(x_{0})\over\prod\limits_{0\leq j\leq n+1\atop j% \neq i}(x_{0}-x_{j})}+{(x_{1}-x_{0})f(x_{1})\over\prod\limits_{0\leq j\leq n+1% \atop j\neq i}(x_{1}-x_{j})}+(x_{1}-x_{0})\sum_{2\leq i\leq n+1}{(x_{1}-x_{0})% f(x_{i})\over\prod\limits_{0\leq j\leq n+1\atop j\neq i}(x_{i}-x_{j})}$ $\displaystyle=(x_{1}-x_{0})\sum_{0\leq i\leq n+1}{f(x_{i})\over\prod\limits_{0% \leq j\leq n+1\atop j\neq i}(x_{i}-x_{j})}$

Thus, we see that, if

 $\Delta^{n}f[x_{0},\ldots,x_{n}]=\sum_{i=0}^{n}{f(x_{i})\over\prod\limits_{0% \leq j\leq n\atop j\neq i}(x_{i}-x_{j})},$

then

 $\Delta^{n+1}f[x_{0},\ldots,x_{n+1}]=\sum_{i=0}^{n+1}{f(x_{i})\over\prod\limits% _{0\leq j\leq n+1\atop j\neq 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

 $\Delta^{n}f[x_{0},\ldots,x_{n}]=\sum_{i=0}^{n}{f(x_{i})\over p^{\prime}(x_{i})}.$

Either form of the explicit formula makes it obvious that divided differences are symmetric functions of $x_{0},x_{1},\ldots$.

Title explicit formula for divided differences ExplicitFormulaForDividedDifferences 2013-03-22 14:41:16 2013-03-22 14:41:16 rspuzio (6075) rspuzio (6075) 21 rspuzio (6075) Definition msc 39A70