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\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 true when $m=0$. Assume that the formula is true for a certain 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$, 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+\mathrm{\cdots }+k_m=0$ is $k_0=\mathrm{\cdots }=k_m=0$, so the sum only consists of one term, $x_0^0\mathrm{\cdots }{x}_m^0=1$ so ${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\cdots }{x}_n]=1$, hence taking further differences produces zero. ∎

Title	divided differences of powers
Canonical name	DividedDifferencesOfPowers
Date of creation	2013-03-22 16:47:59
Last modified on	2013-03-22 16:47:59
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	11
Author	rspuzio (6075)
Entry type	Theorem
Classification	msc 39A70