[proofplan] We use the explicit formula for divided differences at pairwise distinct nodes. This formula writes the [divided difference](/page/Divided%20Difference) as a sum indexed by the nodes, with one term for each node and a denominator formed from all differences against the other nodes. A permutation of the nodes changes only the names of the summation indices, so the sum is invariant under reindexing. [/proofplan]

[step:Write the divided difference using the explicit node formula]Because $x_0,\ldots,x_n$ are pairwise distinct, every factor $x_i-x_j$ with $i\ne j$ is nonzero. Hence the explicit formula for divided differences at distinct nodes gives \begin{align*} f[x_0,\ldots,x_n] = \sum_{i=0}^{n} \frac{f(x_i)}{\prod_{\substack{0\le j\le n, j\ne i}}(x_i-x_j)}. \end{align*} Similarly, the reordered nodes $x_{\sigma(0)},\ldots,x_{\sigma(n)}$ are pairwise distinct because $\sigma:\{0,\ldots,n\}\to\{0,\ldots,n\}$ is bijective. Therefore the same formula gives \begin{align*} f[x_{\sigma(0)},\ldots,x_{\sigma(n)}] = \sum_{k=0}^{n} \frac{f(x_{\sigma(k)})} {\prod_{\substack{0\le \ell\le n, \ell\ne k}}(x_{\sigma(k)}-x_{\sigma(\ell)})}. \end{align*}[/step]

[guided]The main point is that divided differences at distinct nodes admit an explicit formula that depends only on the set of nodes, not on the order in which they are listed. We first verify that the formula is legitimate. Since the numbers $x_0,\ldots,x_n$ are pairwise distinct, if $i\ne j$ then $x_i-x_j\ne 0$. Thus all denominators in \begin{align*} \sum_{i=0}^{n} \frac{f(x_i)}{\prod_{\substack{0\le j\le n, j\ne i}}(x_i-x_j)} \end{align*} are nonzero. The explicit formula for divided differences at distinct nodes therefore gives \begin{align*} f[x_0,\ldots,x_n] = \sum_{i=0}^{n} \frac{f(x_i)}{\prod_{\substack{0\le j\le n, j\ne i}}(x_i-x_j)}. \end{align*} We must also check that the same formula applies after reordering. Since $\sigma$ is a permutation, the map $\sigma:\{0,\ldots,n\}\to\{0,\ldots,n\}$ is bijective. Therefore $x_{\sigma(0)},\ldots,x_{\sigma(n)}$ is again a list of pairwise distinct nodes. Applying the same explicit formula to this reordered list gives \begin{align*} f[x_{\sigma(0)},\ldots,x_{\sigma(n)}] = \sum_{k=0}^{n} \frac{f(x_{\sigma(k)})} {\prod_{\substack{0\le \ell\le n, \ell\ne k}}(x_{\sigma(k)}-x_{\sigma(\ell)})}. \end{align*}[/guided]

[step:Reindex the reordered sum by the original node labels] For each $k\in\{0,\ldots,n\}$, define $i:=\sigma(k)$. Since $\sigma$ is bijective, as $k$ ranges over $\{0,\ldots,n\}$, the index $i$ ranges over $\{0,\ldots,n\}$ exactly once. Moreover, \begin{align*} \{\sigma(\ell):0\le \ell\le n,\ \ell\ne k\} = \{0,\ldots,n\}\setminus\{i\}. \end{align*} Thus, for $i=\sigma(k)$, \begin{align*} \prod_{\substack{0\le \ell\le n, \ell\ne k}}(x_{\sigma(k)}-x_{\sigma(\ell)}) = \prod_{\substack{0\le j\le n, j\ne i}}(x_i-x_j). \end{align*} Substituting this into the reordered formula and reindexing the finite sum gives \begin{align*} f[x_{\sigma(0)},\ldots,x_{\sigma(n)}] = \sum_{i=0}^{n} \frac{f(x_i)}{\prod_{\substack{0\le j\le n, j\ne i}}(x_i-x_j)}. \end{align*} [/step]

[step:Compare the two explicit formulas] The expression obtained for the reordered divided difference is exactly the expression obtained for $f[x_0,\ldots,x_n]$. Therefore \begin{align*} f[x_{\sigma(0)},\ldots,x_{\sigma(n)}]=f[x_0,\ldots,x_n]. \end{align*} This proves that the divided difference is invariant under every permutation of the distinct nodes. [/step]