divided differences of powers

In this entry, we will prove the claims about divided differences of polynomials. Because the divided difference is a linear operator, we can focus our attention on powers.

Theorem 1.

If $f(x)=x^{n}$ and $m\leq n$, then

 $\Delta^{m}f[x_{0},\cdots x_{m}]=\sum_{k_{0}+\cdots+k_{m}=n-m}x_{0}^{k_{0}}% \cdots x_{m}^{k_{m}}.$

If $m>n$, then $\Delta^{m}f[x_{0},\cdots x_{m}]=0$.

Proof.

We proceed by induction. The formula is trivially true when $m=0$. Assume that the formula is true for a certain value of $m$. Then we have

 $\displaystyle\Delta^{m+1}f[x_{0},\cdots x_{m+1}]$ $\displaystyle={\Delta^{m}f[x_{1},x_{2}\cdots x_{m}]-\Delta^{m}f[x_{0},x_{2}% \cdots x_{m}]\over x_{1}-x_{0}}$ $\displaystyle=\sum_{k+k_{2}+\cdots+k_{m}=n-m}{(x_{1}^{k}-x_{0}^{k})x_{2}^{k_{2% }}\cdots x_{m}^{k_{m}}\over x_{1}-x_{0}}$

Using the identity for the sum of a geometric series,

 ${x_{1}^{k}-x_{0}^{k}\over x_{1}-x_{0}}=\sum_{k_{0}+k_{1}=k-1}x_{0}^{k_{0}}x_{1% }^{k_{1}},$

this becomes

 $\displaystyle\Delta^{m+1}f[x_{0},\cdots x_{m+1}]$ $\displaystyle=\sum_{k+k_{2}+\cdots+k_{m}=n-m}\quad\sum_{k_{0}+k_{1}=k-1}x_{0}^% {k_{0}}x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m+1}^{k_{m+1}}$ $\displaystyle=\sum_{k_{0}+k_{1}+k_{2}+\cdots+k_{m}=n-(m+1)}x_{0}^{k_{0}}x_{1}^% {k_{1}}x_{2}^{k_{2}}\cdots x_{m+1}^{k_{m+1}}.$

Note that when $k=0$, we have $x_{1}^{k}-x_{0}^{k}=0$, which is consistent with the formula given above because, in that case, there are no solutions to $k_{1}+k_{2}=k$, so the sum is empty and, by convention, equals zero. Likewise, when $n=m$, then the only solution to $k_{0}+\cdots+k_{m}=0$ is $k_{0}=\cdots=k_{m}=0$, so the sum only consists of one term, $x_{0}^{0}\cdots x_{m}^{0}=1$ so $\Delta^{n}f[x_{0},\cdots x_{n}]=1$, hence taking further differences produces zero. ∎

Title divided differences of powers DividedDifferencesOfPowers 2013-03-22 16:47:59 2013-03-22 16:47:59 rspuzio (6075) rspuzio (6075) 11 rspuzio (6075) Theorem msc 39A70