symmetry of divided differences

Theorem 1.

If $y_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{y}_n$ is a permutation of $x_{\mathrm{0}}\mathrm{,}\mathrm{\dots }\mathrm{,}{x}_n$, then

$${\mathrm{\Delta }}^{n}f[x_0,\mathrm{\dots },x_n]={\mathrm{\Delta }}^{n}f[y_0,\mathrm{\dots },y_n].$$

Proof.

We proceed by induction. When $n=1$, we have, from the definition,

$${\mathrm{\Delta }}^{1}f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0}=\frac{f(x_0)-f(x_1)}{x_0-x_1}={\mathrm{\Delta }}^{1}f[x_1,x_0].$$

Since the only permutations of two elements are the identity and thetransposition, we see that the first divided differrence is symmetric.

Now suppose that we already know that the $n$-th divided differenceis symmetric under permutation of its arguments for some $n\ge 1$.We will prove that the $n+1$-st divided difference is also symmmetricunder all permutations of its arguments.

The divided difference is symmetric under transposing $x_0$ with$x_1$:

${\mathrm{\Delta }}^{n+1}f[x_0,x_1,x_2,\mathrm{\dots },x_{n+1}]$$={\displaystyle \frac{{\mathrm{\Delta }}^{n}f[x_1,x_2,\mathrm{\dots }{x}_{n+1}]-{\mathrm{\Delta }}^{n}f[x_0,x_2,\mathrm{\dots }{x}_{n+1}]}{x_1-x_0}}$

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

$={\mathrm{\Delta }}^{n+1}f[x_1,x_0,x_2,\mathrm{\dots },x_{n+1}]$

The divided difference is symmetric under transposing $x_1$ with$x_2$:

${\mathrm{\Delta }}^{n+1}$$f[x_0,x_1,x_2,\mathrm{\dots },x_{n+1}]$

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

$={\displaystyle \frac{\begin{array}{c}\hfill \left(x_2-x_0\right)\left({\mathrm{\Delta }}^{n-1}f[x_2,x_3\mathrm{\dots }{x}_{n+1}]-{\mathrm{\Delta }}^{n-1}f[x_1,x_3\mathrm{\dots }{x}_{n+1}]\right)\hfill \\ \hfill -\left(x_2-x_1\right)\left({\mathrm{\Delta }}^{n-1}f[x_2,x_3\mathrm{\dots }{x}_{n+1}]-{\mathrm{\Delta }}^{n-1}f[x_0,x_3\mathrm{\dots }{x}_{n+1}]\right)\hfill \end{array}}{(x_2-x_1)(x_1-x_0)(x_2-x_0)}}$

$={\displaystyle \frac{\begin{array}{c}\hfill \left(x_1-x_0\right)\left({\mathrm{\Delta }}^{n-1}f[x_1,x_3\mathrm{\dots }{x}_{n+1}]-{\mathrm{\Delta }}^{n-1}f[x_2,x_3\mathrm{\dots }{x}_{n+1}]\right)\hfill \\ \hfill -\left(x_1-x_2\right)\left({\mathrm{\Delta }}^{n-1}f[x_1,x_3\mathrm{\dots }{x}_{n+1}]-{\mathrm{\Delta }}^{n-1}f[x_0,x_3\mathrm{\dots }{x}_{n+1}]\right)\hfill \end{array}}{(x_1-x_2)(x_1-x_0)(x_2-x_0)}}$

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

$={\mathrm{\Delta }}^{n+1}f[x_0,x_2,x_1,\mathrm{\dots },x_{n+1}]$

The divided difference is symmetric under transposing$x_k$ with $x_{k+1}$ when $k>1$:

${\mathrm{\Delta }}^{n+1}$$f[x_0,x_1,x_2,\mathrm{\dots },x_k,x_{k+1},\mathrm{\dots },x_{n+1}]$

$={\displaystyle \frac{{\mathrm{\Delta }}^{n}f[x_1,x_2,\mathrm{\dots },x_k,x_{k+1},\mathrm{\dots },x_{n+1}]-{\mathrm{\Delta }}^{n}f[x_0,x_2,\mathrm{\dots },x_k,x_{k+1},\mathrm{\dots },x_{n+1}]}{x_1-x_0}}$

$={\displaystyle \frac{{\mathrm{\Delta }}^{n}f[x_1,x_2,\mathrm{\dots },x_{k+1},x_k,\mathrm{\dots },x_{n+1}]-{\mathrm{\Delta }}^{n}f[x_0,x_2,\mathrm{\dots },x_{k+1},x_k,\mathrm{\dots },x_{n+1}]}{x_1-x_0}}$

$={\mathrm{\Delta }}^{n+1}f[x_0,x_1,x_2,\mathrm{\dots },x_{k+1},x_k,\mathrm{\dots },x_{n+1}]$

Since any permutation of $x_0,x_1,\mathrm{\dots }{x}_{n+1}$ can begenreated from the transpositions of $x_k$ with $x_{k+1}$for $k$ between $0$ and $n$, it follows that${\mathrm{\Delta }}^{n+1}f[x_0,x_1,\mathrm{\dots },x_k,x_{k+1},\mathrm{\dots },x_{n+1}]$is symmetric under all permutaions of $x_0,x_1,\mathrm{\dots }{x}_{n+1}$.∎