# symmetry of divided differences

###### Theorem 1.

If $y_{0},\ldots,y_{n}$ is a permutation of $x_{0},\ldots,x_{n}$, then

 $\Delta^{n}f[x_{0},\ldots,x_{n}]=\Delta^{n}f[y_{0},\ldots,y_{n}].$
###### Proof.

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

 $\Delta^{1}f[x_{0},x_{1}]={f(x_{1})-f(x_{0})\over x_{1}-x_{0}}={f(x_{0})-f(x_{1% })\over x_{0}-x_{1}}=\Delta^{1}f[x_{1},x_{0}].$

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

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

The divided difference is symmetric under transposing $x_{0}$ with $x_{1}$:

 $\displaystyle\Delta^{n+1}f[x_{0},x_{1},x_{2},\ldots,x_{n+1}]$ $\displaystyle={\Delta^{n}f[x_{1},x_{2},\ldots x_{n+1}]-\Delta^{n}f[x_{0},x_{2}% ,\ldots x_{n+1}]\over x_{1}-x_{0}}$ $\displaystyle={\Delta^{n}f[x_{0},x_{2},\ldots x_{n+1}]-\Delta^{n}f[x_{1},x_{2}% ,\ldots x_{n+1}]\over x_{0}-x_{1}}$ $\displaystyle=\Delta^{n+1}f[x_{1},x_{0},x_{2},\ldots,x_{n+1}]$

The divided difference is symmetric under transposing $x_{1}$ with $x_{2}$:

 $\displaystyle\Delta^{n+1}$ $\displaystyle f[x_{0},x_{1},x_{2},\ldots,x_{n+1}]$ $\displaystyle={\Delta^{n}f[x_{1},x_{2},\ldots x_{n+1}]-\Delta^{n}f[x_{0},x_{2}% ,\ldots x_{n+1}]\over x_{1}-x_{0}}$ $\displaystyle={\begin{matrix}(x_{2}-x_{0})\left(\Delta^{n-1}f[x_{2},x_{3}% \ldots x_{n+1}]-\Delta^{n-1}f[x_{1},x_{3}\ldots x_{n+1}]\right)\\ -(x_{2}-x_{1})\left(\Delta^{n-1}f[x_{2},x_{3}\ldots x_{n+1}]-\Delta^{n-1}f[x_{% 0},x_{3}\ldots x_{n+1}]\right)\end{matrix}\over(x_{2}-x_{1})(x_{1}-x_{0})(x_{2% }-x_{0})}$ $\displaystyle={\begin{matrix}(x_{1}-x_{0})\Delta^{n-1}f[x_{2},x_{3}\ldots x_{n% +1}]&-&(x_{2}-x_{0})\Delta^{n-1}f[x_{1},x_{3}\ldots x_{n+1}]\\ &+&(x_{2}-x_{1})\Delta^{n-1}f[x_{0},x_{3}\ldots x_{n+1}]\end{matrix}\over(x_{2% }-x_{1})(x_{1}-x_{0})(x_{2}-x_{0})}$ $\displaystyle={\begin{matrix}(x_{1}-x_{0})\left(\Delta^{n-1}f[x_{1},x_{3}% \ldots x_{n+1}]-\Delta^{n-1}f[x_{2},x_{3}\ldots x_{n+1}]\right)\\ -(x_{1}-x_{2})\left(\Delta^{n-1}f[x_{1},x_{3}\ldots x_{n+1}]-\Delta^{n-1}f[x_{% 0},x_{3}\ldots x_{n+1}]\right)\end{matrix}\over(x_{1}-x_{2})(x_{1}-x_{0})(x_{2% }-x_{0})}$ $\displaystyle={\Delta^{n}f[x_{2},x_{1},\ldots x_{n+1}]-\Delta^{n}f[x_{0},x_{1}% ,\ldots x_{n+1}]\over x_{1}-x_{0}}$ $\displaystyle=\Delta^{n+1}f[x_{0},x_{2},x_{1},\ldots,x_{n+1}]$

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

 $\displaystyle\Delta^{n+1}$ $\displaystyle f[x_{0},x_{1},x_{2},\ldots,x_{k},x_{k+1},\ldots,x_{n+1}]$ $\displaystyle={\Delta^{n}f[x_{1},x_{2},\ldots,x_{k},x_{k+1},\ldots,x_{n+1}]-% \Delta^{n}f[x_{0},x_{2},\ldots,x_{k},x_{k+1},\ldots,x_{n+1}]\over x_{1}-x_{0}}$ $\displaystyle={\Delta^{n}f[x_{1},x_{2},\ldots,x_{k+1},x_{k},\ldots,x_{n+1}]-% \Delta^{n}f[x_{0},x_{2},\ldots,x_{k+1},x_{k},\ldots,x_{n+1}]\over x_{1}-x_{0}}$ $\displaystyle=\Delta^{n+1}f[x_{0},x_{1},x_{2},\ldots,x_{k+1},x_{k},\ldots,x_{n% +1}]$

Since any permutation of $x_{0},x_{1},\ldots x_{n+1}$ can be genreated from the transpositions of $x_{k}$ with $x_{k+1}$ for $k$ between $0$ and $n$, it follows that $\Delta^{n+1}f[x_{0},x_{1},\ldots,x_{k},x_{k+1},\ldots,x_{n+1}]$ is symmetric under all permutaions of $x_{0},x_{1},\ldots x_{n+1}$. ∎

Title symmetry of divided differences SymmetryOfDividedDifferences 2013-03-22 16:48:29 2013-03-22 16:48:29 rspuzio (6075) rspuzio (6075) 22 rspuzio (6075) Theorem msc 39A70