Showing that Newton's divided difference formulas are invariant to permutations of points by swapping neigbhoring points

Question

This is not the right way to prove that the Newton's divided difference formula is invariant to permutations, I just want to see if this kind of proof could be made to work.

We have a set of points $(x_0, \dots, x_n), x_i < x_{i+1}$, with corresponding function values $f(x_i) = f_i$.

The goal is to show that the Newton's divided difference formula is invariant for the permutation of points $\{x_i\}_{i \in I}$.

The divided difference of two adjacent points

$f[x_i, x_{i+1}] = \dfrac{f_{i+1} - f_i}{x_{i+1} - x_i}$

If $x_i$ is swapped with $x_{i+1}$

$f[x_{i+1}, x_i] = f[swap(x_i, x_{i+1})] = \dfrac{-(f_{i+1} - f_i)}{-(x_{i+1} - x_i)}=f[x_i, x_{i+1}]$. (1)

A permutation of $(x_0, x_1, \dots, x_i)$ can be defined as a swap operation that exchanges some $x_k, x_l, k < l$. This swap operation can be constructed from two iterative swap operations that operate successively on neighboring points. The first one swaps the argument with forward-adjacent points starting with $x_k, x_{k+1}$ until $x_l$ is replaced by $x_k$.

The second iteration of swaps sends $x_k$ to $x_l$ using backward-adjacent point substitution. This iteration reverses the effect of forward swap operations from the previous step.

I am not sure how to write this down, here is my attempt:

$swap(x_k, x_l) = swap_{i=k}^{l-1}(x_i, x_{i+1}), swap_{i=k-1}^{l+1}(x_i, x_{i-1})$

If $k>l$ then the indexes are switched.

Example: Exchange (1,4) by succesive swap operations

Forward swaps $i=[l, k-1], swap(i, i+1)$

$ \begin{bmatrix} 0\\ 1\\ 2\\ 3\\ 4 \end{bmatrix} \rightarrow \begin{bmatrix} 0\\ 2\\ 1\\ 3\\ 4 \end{bmatrix} \rightarrow \begin{bmatrix} 0\\ 2\\ 3\\ 1\\ 4 \end{bmatrix} \rightarrow \begin{bmatrix} 0\\ 2\\ 3\\ 4\\ 1 \end{bmatrix} $

Backward swaps $i=[k-1, l+1], swap(i, i-1)$

$ \begin{bmatrix} 0\\ 2\\ 3\\ 4\\ 1 \end{bmatrix}\rightarrow \begin{bmatrix} 0\\ 2\\ 4\\ 3\\ 1 \end{bmatrix} \rightarrow \begin{bmatrix} 0\\ 4\\ 2\\ 3\\ 1 \end{bmatrix} $

Because (1) shows that the divided difference formula is invariant for swapping adjacent points, and any permutation of $(x_0, \dots, x_n)$ can be defined using sequences of adjacent point swaps, the divided difference formula is invariant to permutations.

Answer 1

Showing that Newton's Divided formula is permutation invariant in $f[x_{i+1},x_i]$ is not enough to claim that it will work for $f[x_0,x_1,...,x_i,x_{i+1},...x_k]$, cause there will be many terms which will involve $f[x_{i+1},x_i]$ after they are broken down using the recursive formula and there will be parts like $f[x_0,x_1,...,x_i]$ and $f[x_{i+1},...,x_k]$ where $x_i$ and $x_{i+1}$ are on different terms so swapping $x_i$ and $x_{i+1}$ will also change these terms and you need to show that it will remain invariant.

Here is my approach:
We have to show that Newton's Divided formula is permutation invariant, i.e. if $\pi$ is any permutation of {0, 1, 2, 3, 4, ..., k}, then
$$f[x_0,x_1,x_2,..,x_i,x_{i+1},..,x_k] = f[x_{\pi(0)},x_{\pi(1)},x_{\pi(2)},..,x_{\pi(i+1)},x_{\pi(i)},..,x_{\pi(k)}]$$ We can start by having a look at simple cases (In order to verify that the statement is actually true or not):

• k = 0 : $f[x_0] = f[x_0]$ which is trivially true.
• k = 1 : $f[x_0, x_1] = \frac{f[x_0] - f[x_1]}{x_0 - x_1} = \frac{f[x_1] - f[x_0]}{x_1 - x_0} = f[x_1, x_0]$ so it is permutation invariant under this case.

In general if you see carefully then we can figure out an pattern for the Newton's Divided Difference Formula. Like:

• k = 0: $f[x_0] = f(x_0)$
• k = 1: $f[x_0, x_1] = \frac{f(x_0) - f(x_1)}{x_0 - x_1}$
• k = 2: $f[x_0, x_1, x_2] = \frac{f[x_0,x_1] - f[x_1,x_2]}{x_0 - x_2} = \frac{f(x_0)\cdot(x_1-x_2) - f(x_1)\cdot(x_0-x_2) + f(x_2)\cdot(x_0-x_1)}{(x_0 - x_1)\cdot(x_0 - x_2)\cdot(x_1 - x_2)}$, we can see some pattern building, Let's do one more step
• k =3: $f[x_0, x_1, x_2, x_3] = \frac{f[x_0,x_1, x_2] - f[x_1,x_2,x_3]}{x_0 - x_3} = \frac{f(x_0)\cdot(x_1-x_2)\cdot(x_2-x_3)\cdot(x_1-x_3) - f(x_1)\cdot(x_0-x_2)\cdot(x_2-x_3)\cdot(x_0-x_3) + f(x_2)\cdot(x_0-x_1)\cdot(x_1-x_3)\cdot(x_0-x_3) - f(x_3)\cdot(x_0-x_1)\cdot(x_1-x_2)\cdot(x_0-x_2)}{(x_0 - x_1)\cdot(x_0 - x_2)\cdot(x_0 - x_3)\cdot(x_1-x_2)\cdot(x_1-x_3)\cdot(x_2-x_3)}$

Now the pattern seems clear and we can write in compact notation: $$f[x_0,x_1,x_2,...,x_k] = \frac{\sum_{i=0}^{k}(-1)^{i}\cdot f(x_i)\cdot(\prod_{m=0,m\neq i,i-1}^{k-1}(x_m - x_{m+1}))\cdot(x_c-x_d)}{\prod_{i=0}^{k-1}\prod_{j=i+1}^{k}(x_i - x_j)}$$ where $c = \left\{ \begin{array}{ll} 0 & i\neq 0 \\ 1 & i = 0 \end{array} \right. $ and $d = \left\{ \begin{array}{ll} k & i\neq k \\ k-1 & i = k \end{array} \right. $
Now we can see that interchanging $x_p$ and $x_{p+1}$ in Newton's Divided Difference formula for k terms causes change in only 1 term in the product of the denominator that is $(x_p - x_{p+1})$ changes to $(x_{p+1} - x_p)$ so we can take -1 common and the denominator is now same as it was before the swap.
Similarly, we can see that in the numerator the position of the $p^{th}$ indexed term and $(p+1)^{th}$ indexed term are interchanged and in all other terms $(x_p - x_{p+1})$ has changed to $(x_{p+1} - x_p)$. Hence, we can again take -1 common and the numerator is now same as it was before swap
Both the -1 taken out common cancels and we get that Newton's Divided formula is invariant under swap of a pair of adjacent terms.
Note that this is enough to prove that the formula is invariant under any permutation as we can represent any permutation as a sequence of adjacent swaps.
Hence, Proved.