divided differences of powers

In this entry, we will prove the claims about divided differencesof polynomials. Because the divided difference is a linearoperator, we can focus our attention on powers.

Theorem 1.

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

$${\mathrm{\Delta }}^{m}f[x_0,\mathrm{\cdots }{x}_m]=\sum _{k_0+\mathrm{\cdots }+k_m=n-m}{x}_0^{k_0}\mathrm{\cdots }{x}_m^{k_m}.$$

If $m\mathrm{>}n$, then ${\mathrm{\Delta }}^m\mathit{}f\mathit{}\mathrm{[}{x}_{\mathrm{0}}\mathrm{,}\mathrm{\cdots }\mathit{}{x}_m\mathrm{]}\mathrm{=}\mathrm{0}$.

Proof.

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

${\mathrm{\Delta }}^{m+1}f[x_0,\mathrm{\cdots }{x}_{m+1}]$$={\displaystyle \frac{{\mathrm{\Delta }}^{m}f[x_1,x_2\mathrm{\cdots }{x}_m]-{\mathrm{\Delta }}^{m}f[x_0,x_2\mathrm{\cdots }{x}_m]}{x_1-x_0}}$

$={\displaystyle \sum _{k+k_2+\mathrm{\cdots }+k_m=n-m}}{\displaystyle \frac{(x_1^k-x_0^k)x_2^{k_2}\mathrm{\cdots }{x}_m^{k_m}}{x_1-x_0}}$

Using the identity for the sum of a geometric series,

$$\frac{x_1^k-x_0^k}{x_1-x_0}=\sum _{k_0+k_1=k-1}{x}_0^{k_0}{x}_1^{k_1},$$

this becomes

${\mathrm{\Delta }}^{m+1}f[x_0,\mathrm{\cdots }{x}_{m+1}]$$={\displaystyle \sum _{k+k_2+\mathrm{\cdots }+k_m=n-m}}\mathit{\hspace{1em}}{\displaystyle \sum _{k_0+k_1=k-1}}{x}_0^{k_0}{x}_1^{k_1}{x}_2^{k_2}\mathrm{\cdots }{x}_{m+1}^{k_{m+1}}$

$={\displaystyle \sum _{k_0+k_1+k_2+\mathrm{\cdots }+k_m=n-(m+1)}}{x}_0^{k_0}{x}_1^{k_1}{x}_2^{k_2}\mathrm{\cdots }{x}_{m+1}^{k_{m+1}}.$

Note that when $k=0$, we have $x_1^k-x_0^k=0$, whichis consistent with the formula given above because, in thatcase, there are no solutions to $k_1+k_2=k$, so thesum is empty and, by convention, equals zero. Likewise,when $n=m$, then the only solution to $k_0+\mathrm{\cdots }+k_m=0$is $k_0=\mathrm{\cdots }=k_m=0$, so the sum only consists ofone term, $x_0^0\mathrm{\cdots }{x}_m^0=1$ so${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\cdots }{x}_n]=1$, hence takingfurther differences produces zero.∎