PlanetMath: divided differences of powers

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. $\qedsymbol$