Show that$$\sum_{1\le i<j\le n}\left((x_j-x_i)-(x_j-x_i)^2\right)=\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\\=-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}.$$
I wonder how this identity comes up with the first and second recipes? Can anyone explain this in detail? I got this identity when I was reading the problem here. Thanks.
On
This was a pain, but here it is.
$\begin{array}\\ s(n) &=\sum_{1\le i<j\le n}\left((x_{j}-x_{i})-(x_{j}-x_{i})^2\right)\\ &=\sum_{i=1}^n \sum_{j=i+1}^n((x_{j}-x_{i})-(x_{j}-x_{i})^2)\\ &=\sum_{i=1}^n \sum_{j=i+1}^n(x_{j}-x_{i})-\sum_{i=1}^n \sum_{j=i+1}^n(x_{j}-x_{i})^2\\ &=s_1(n)-s_2(n)\\ s_1(n) &=\sum_{i=1}^n \sum_{j=i+1}^n(x_{j}-x_{i})\\ &=\sum_{i=1}^n \sum_{j=i}^n(x_{j}-x_{i})\\ &=\sum_{i=1}^n \sum_{j=i}^nx_{j}-\sum_{i=1}^n \sum_{j=i}^nx_{i}\\ &=\sum_{j=1}^n \sum_{i=1}^jx_{j}-\sum_{i=1}^n (n-i+1)x_{i}\\ &=\sum_{j=1}^n x_j\sum_{i=1}^j1-\sum_{i=1}^n (n-i+1)x_{i}\\ &=\sum_{j=1}^n jx_j-\sum_{i=1}^n (n-i+1)x_{i}\\ &=\sum_{i=1}^n ix_i-\sum_{i=1}^n (n-i+1)x_{i}\\ &=\sum_{i=1}^n (i-n+i-1)x_i\\ &=\sum_{i=1}^n (2i-n-1)x_i\\ s_2(n) &=\sum_{i=1}^n \sum_{j=i+1}^n(x_{j}-x_{i})^2\\ &=\sum_{i=1}^n \sum_{j=i}^n(x_{j}-x_{i})^2\\ &=\sum_{i=1}^n \sum_{j=i}^n(x_j^2-2x_jx_i+x_i^2)\\ &=\sum_{i=1}^n \sum_{j=i}^nx_j^2-2\sum_{i=1}^n \sum_{j=i}^nx_jx_i+\sum_{i=1}^n \sum_{j=i}^nx_i^2\\ &=s_3(n)-2s_4(n)+s_5(n)\\ s_3(n) &=\sum_{i=1}^n \sum_{j=i}^nx_j^2\\ &=\sum_{j=1}^n \sum_{i=1}^jx_j^2\\ &=\sum_{j=1}^n jx_j^2\\ s_4(n) &=\sum_{i=1}^n \sum_{j=i}^nx_jx_i\\ &=\sum_{i=1}^n x_i\sum_{j=i}^nx_j\\ &=\sum_{i=1}^n x_i(\sum_{j=1}^nx_j-\sum_{j=1}^{i-1}x_j)\\ &=\sum_{i=1}^n x_i\sum_{j=1}^nx_j-\sum_{i=1}^n \sum_{j=1}^{i-1}x_ix_j\\ &=(\sum_{i=1}^n x_i)^2-\sum_{j=1}^{n-1} \sum_{i=j+1}^{n}x_ix_j\\ &=(\sum_{i=1}^n x_i)^2-\sum_{j=1}^{n-1} x_j\sum_{i=j+1}^{n}x_i\\ &=(\sum_{i=1}^n x_i)^2-\sum_{j=1}^{n} x_j\sum_{i=j+1}^{n}x_i\\ &=(\sum_{i=1}^n x_i)^2-\sum_{j=1}^{n} x_j(\sum_{i=j}^{n}x_i-x_j)\\ &=(\sum_{i=1}^n x_i)^2-\sum_{j=1}^{n} x_j\sum_{i=j}^{n}x_i+\sum_{j=1}^{n} x_j^2\\ &=(\sum_{i=1}^n x_i)^2-\sum_{i=1}^{n} x_i\sum_{j=i}^{n}x_j+\sum_{j=1}^{n} x_j^2\\ &=(\sum_{i=1}^n x_i)^2-s_4(n)+\sum_{j=1}^{n} x_j^2\\ \text{so}\\ s_4(n) &=\frac12((\sum_{i=1}^n x_i)^2+\sum_{i=1}^{n} x_i^2)\\ s_5(n) &=\sum_{i=1}^n \sum_{j=i}^nx_i^2\\ &=\sum_{i=1}^n (n-i+1)x_i^2\\ \text{so}\\ s_2(n) &=s_3(n)-2s_4(n)+s_5(n)\\ &=\sum_{j=1}^n jx_j^2-((\sum_{i=1}^n x_i)^2+\sum_{i=1}^{n} x_i^2)+\sum_{i=1}^n (n-i+1)x_i^2\\ &=-((\sum_{i=1}^n x_i)^2+\sum_{i=1}^{n} x_i^2)+\sum_{i=1}^n (n+1)x_i^2\\ &=-(\sum_{i=1}^n x_i)^2+n\sum_{i=1}^n x_i^2\\ \text{so}\\ s(n) &=s_1(n)-s_2(n)\\ &=\sum_{i=1}^n (2i-n-1)x_i-(n\sum_{i=1}^n x_i^2-(\sum_{i=1}^n x_i)^2)\\ &=(\sum_{i=1}^n x_i)^2-n\sum_{i=1}^n x_i^2+\sum_{i=1}^n (2i-n-1)x_i\\ \end{array} $
Whew!
On
An alternative to @martycohen's approach, using derivatives. I think that if I didn't have to write out details about the Kronecker delta, this might be shorter than Marty's, but I can't promist that.
Both sides are evidently quadratics in the $x_i$ variables, with no constant terms. That is to say, they have the form $$ H = (\sum_{ij} c_{ij} x_i x_j ) + \sum_i e_i x_i $$ If we differentiate such a thing with respect to $x_k$, we get $$ \frac{\partial H}{\partial x_k} = (\sum_i c_{ik} x_i + \sum_j c_{kj} x_j) + e_k, $$ and if we set all the $x_i$ to zero, we get just $e_k$. Similarly, if we differentiate twice, we can find $c_{kp}$. By comparing these for the two sides, we'll see the two quadratics are equal.
The derivative of $x_i$ with respect to $x_k$ is $\delta_{ik} = \begin{cases} 1 & i = k\\ 0 & i \ne k \end{cases}$, and $\sum_i x_i \delta_{ik} = x_k$, which we'll use frequently in various forms. Also note that $$ \tag{sum-j} \sum_{i =1}^n \sum_{j = i+1}^n \delta_{jk} = k-1, $$ because the inner sum is either $0$ or $1$; it's $1$ whenever $k > i$. This occurs, in the outer sum, for $i = 1, 2, \ldots, k-1$, i.e., $k-1$ times. Similarly, $$ \tag{sum-i} \sum_{i =1}^n \sum_{j = i+1}^n \delta_{ik} = n-k. $$ Finally, $$ \tag{sum-pk} \sum_{i =1}^n \sum_{j = i+1}^n \delta_{ik}\delta_{jp} = \sum_{j = k+1}^n \delta_{jp} = \delta_{k < p}, $$ by which I mean the sum is $1$ if $k < p$, and $0$ otherwise.
Returning to the main equation, and calling the left and right-hand expressions $L$ and $R$, we'll check first to see that the linear-term coefficient of $x_k$ is identical in both.
The derivative of the LHS with respect to $x_k$ is \begin{align} \frac{\partial L}{\partial x_k} &= \sum_{i=1}^n \sum_{j = i+1}^n \frac{\partial \left((x_{j}-x_{i})-(x_{j}-x_{i})^2\right) } {\partial x_k}\\ & = \sum_{i=1}^n \sum_{j = i+1}^n \left((\delta_{jk}-\delta_{ik})-2(x_{j}-x_{i})(\delta_{jk}-\delta_{ik})\right) \end{align} Evaluated when all the $x_i$ are zero, we get \begin{align} \frac{\partial L}{\partial x_k}(0,0,\ldots, 0) & = \sum_{i=1}^n \sum_{j = i+1}^n (\delta_{jk}-\delta_{ik})\\ & = \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jk}-\sum_{i=1}^n \sum_{j = i+1}^n\delta_{ik}\\ & = (k-1) - (n-k) & \text{by sum-i and sum-j above} \\ &= -n + 2k - 1. \end{align}
The derivative of the right-hand side is \begin{align} \frac{\partial R}{\partial x_k} &= \frac{\partial \biggl[ \big(\sum_{i=1}^n{x_i}\big)^2-n\sum_{i=1}^n{x_i^2} - \sum_{i=1}^n{(n-2i+1)x_i}\biggr]}{\partial x_k}\\ &= 2\big(\sum_{i=1}^n{x_i}\big) \sum_{i=1}^n \delta_{ik} -n \frac{\partial \sum_{i=1}^n{x_i^2}}{\partial x_k} - \frac{\partial \sum_{i=1}^n{(n-2i+1)x_i}}{\partial x_k} \\ &= 2\big(\sum_{i=1}^n{x_i}\big) -n \biggl[ \sum_{i=1}^n{2x_i \delta_{ik}} \biggr] - \sum_{i=1}^n {(n-2i+1)\delta_{ik}} \\ &= 2\big(\sum_{i=1}^n{x_i}\big) -2n x_k - {(n-2k+1)} \\ \end{align} When $x_1 = x_2 = \ldots = x_n = 0$, we again get a value of $-(n-2k + 1) = -n + 2k - 1$. So the linear terms on the two sides are equal.
Now let's look at the second derivatives. We have \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = \sum_{i=1}^n \sum_{j = i+1}^n \left(-2(\delta_{jp}-\delta_{ip})(\delta_{jk}-\delta_{ik})\right)\\ & = -2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jp}\delta_{jk} - \delta_{jp}\delta_{ik}-\delta_{ip}\delta_{jk} + \delta_{ip}\delta_{ik} \end{align} First consider the case $k = p$: \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = -2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jk}\delta_{jk} - \delta_{jk}\delta_{ik}-\delta_{ik}\delta_{jk} + \delta_{ik}\delta_{ik}\\ & = -2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jk} - 2\delta_{jk}\delta_{ik} + \delta_{ik}\\ & = -2\biggl[ (k-1) + (n-k) - 2\sum_{i=1}^n \sum_{j = i+1}^n \delta_{jk}\delta_{ik} \biggr] & \text{by sum-i and sum-j}\\ \end{align} The remaining product $\delta_{jk}\delta_{ik}$ is $1$ only if $i$ and $j$ are equal, but since $j$ starts at $i+1$, this never happens. Hence \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = 2 - 2n \end{align} in the case where $k = p$.
Now look at $k \ne p$. We have \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = -2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jp}\delta_{jk} + 2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{jp}\delta_{ik} + 2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{ip}\delta_{jk} - 2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{ip}\delta_{ik} \end{align} By sum-kp, the two middle terms are $\delta_{k < p}$ and $\delta_{p<k}$, so exactly one of them is $1$, and we can replace their sum with a $1$ (which gets multiplied by the $2$ in front!). So we have \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = 2 -2 \sum_{i=1}^n \sum_{j = i+1}^n\delta_{jp}\delta_{jk} - 2 \sum_{i=1}^n \sum_{j = i+1}^n \delta_{ip}\delta_{ik} \\ \end{align} Furthermore, because $k$ and $p$ are distinct, $j$ cannot equal both of them, so the first sun is zero; similarly for the second. We end up with \begin{align} \frac{\partial^2 L}{\partial x_k \partial x_p} & = 2 \end{align}
On the right-hand side, we have \begin{align} \frac{\partial R}{\partial x_k} &= 2\big(\sum_{i=1}^n{x_i}\big) -2n x_k - {(n-2k+1)} \\ \end{align} we get \begin{align} \frac{\partial^2 R}{\partial x_k \partial x_p} &= 2\big(\sum_{i=1}^n{ \delta_{ip}}\big) -2n \delta_{kp} \\ &= 2 -2n \delta_{kp} \\ \end{align} which agrees exactly with the result for the left-hand side. We're done!
On
$\def\peq{\mathrel{\phantom{=}}{}}$For the first identity, because$$ \sum_{i < j} (x_j - x_i) = \sum_{k = 1}^n x_k \left( \sum_{l < k} 1 + \sum_{l > k} (-1) \right) = \sum_{k = 1}^n (2k - n - 1) x_k, $$\begin{gather*} \sum_{i < j} (x_j - x_i)^2 = \sum_{k = 1}^n x_k^2 \left( \sum_{l < k} 1 + \sum_{l > k} 1 \right) - 2 \sum_{i < j} x_i x_j\\ = (n - 1) \sum_{k = 1}^n x_k^2 - \left( \left( \sum_{k = 1}^n x_k \right)^2 - \sum_{k = 1}^n x_k^2 \right) = n \sum_{k = 1}^n x_k^2 - \left( \sum_{k = 1}^n x_k \right)^2, \end{gather*} then$$ \sum_{i < j} ((x_j - x_i) - (x_j - x_i)^2) = \left( \sum_{k = 1}^n x_k \right)^2 - n \sum_{k = 1}^n x_k^2 - \sum_{k = 1}^n (n - 2k + 1) x_k. $$
For the second identity, denoting $\bar{x} = \dfrac{1}{n} \sum\limits_{k = 1}^n x_k$,\begin{align*} &\peq -n \sum_{k = 1}^n \left( x_k - \bar{x} + \frac{1}{2n} (n - 2k + 1) \right)^2 + \frac{1}{4n} \sum_{k = 1}^n (n - 2k + 1)^2\\ &= -\sum_{k = 1}^n \left( n(x_k - \bar{x})^2 + (n - 2k + 1)(x_k - \bar{x}) + \frac{1}{4n} (n - 2k + 1)^2 \right) + \frac{1}{4n} \sum_{k = 1}^n (n - 2k + 1)^2\\ &= -\sum_{k = 1}^n \left( n(x_k - \bar{x})^2 + (n - 2k + 1)(x_k - \bar{x}) \right)\\ &= -n \sum_{k = 1}^n (x_k - \bar{x})^2 - \sum_{k = 1}^n (n - 2k + 1) x_k + \bar{x} \sum_{k = 1}^n (n - 2k + 1)\\ &= -n \left( \sum_{k = 1}^n x_k^2 - n\bar{x}^2 \right) - \sum_{k = 1}^n (n - 2k + 1) x_k + 0\\ &= \left( \sum_{k = 1}^n x_k \right)^2 - n \sum_{k = 1}^n x_k^2 - \sum_{k = 1}^n (n - 2k + 1) x_k. \end{align*}
On
We take an algebraic approach and consider the expressions as quadratic polynomials in $n$ variables $x_1,x_2,\ldots,x_n$. We show equality by comparing the coefficients of corresponding terms.
It is convenient to use the coefficient of operator $[x^n]$ to denote the coefficient of $x^n$ of a series.
We introduce $f_1,f_2,f_3$ as \begin{align*} f_1(x_1,\ldots,x_n)&=\sum_{1\leq i<j\leq n}\left(\left(x_j-x_i\right)-\left(x_j-x_i\right)^2\right)\\ f_2(x_1,\ldots,x_n)&=\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\\ f_3(x_1,\ldots,x_n)&=-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2} \end{align*}
We start with the square terms.
We obtain for $1\leq k\leq n$: \begin{align*} \color{blue}{[x_k^2]f_1(x_1,\ldots,x_n)}&=[x_k^2]\sum_{1\leq i<j\leq n}\left(\left(x_j-x_i\right)-\left(x_j-x_i\right)^2\right)\\ &=-[x_k^2]\sum_{1\leq i<j\leq n}\left(x_j-x_i\right)^2\\ &=-[x_k^2]\sum_{1\leq i<k}\left(x_k-x_i\right)^2-[x_k^2]\sum_{k<j\leq n}\left(x_j-x_k\right)^2\\ &=-(k-1)-(n-k)\\ &\,\,\color{blue}{=1-n}\\ \color{blue}{[x_k^2]f_2(x_1,\ldots,x_n)}&=[x_k^2]\left(\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\right)\\ &=[x_k^2]\sum_{i=1}^nx_i^2-n[x_k^2]\sum_{i=1}^nx_i^2\\ &\,\,\color{blue}{=1-n}\\ \color{blue}{[x_k^2]f_3(x_1,\ldots,x_n)}&=[x_k^2]\left(-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\right.\\ &\qquad\qquad\qquad\left.+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\right)\\ &=-n[x_k^2]\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\\ &=-n[x_k^2]\sum_{i=1}^n\left(x_i^2-2x_i\cdot\frac{1}{n}\sum_{j=1}^n{x_j}+\left(\frac1n\sum_{j=1}^n{x_j}\right)^2\right)\\ &=-n[x_k^2]\sum_{i=1}^nx_i^2+2[x_k^2]\sum_{i=1}^nx_i\sum_{j=1}^nx_j-\frac{1}{n}[x_k^2]\sum_{i=1}^n\left(\sum_{j=1}^n{x_j}\right)^2\\ &=-n+2-1\\ &\,\,\color{blue}{=1-n} \end{align*}
Now we check the mixed quadratic terms.
We obtain for $1\leq k<l\leq n$: \begin{align*} \color{blue}{[x_kx_l]f_1(x_1,\ldots,x_n)}&=[x_kx_l]\sum_{1\leq i<j\leq n}\left(\left(x_j-x_i\right)-\left(x_j-x_i\right)^2\right)\\ &=-[x_kx_l]\sum_{1\leq i<j\leq n}\left(x_j-x_i\right)^2\\ &=2[x_kx_l]\sum_{1\leq i<j\leq n}x_ix_j\\ &\,\,\color{blue}{=2}\\ \color{blue}{[x_kx_l]f_2(x_1,\ldots,x_n)}&=[x_kx_l]\left(\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\right)\\ &=[x_kx_l]\left(\sum_{i=1}^n{x_i}\right)^2\\ &=[x_kx_l]\left(\sum_{i=1}^n{x_i}^2+2\sum_{1\leq i<j\leq n}x_ix_j\right)\\ &\,\,\color{blue}{=2}\\ \color{blue}{[x_kx_l]f_3(x_1,\ldots,x_n)}&=[x_k^2]\left(-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\right.\\ &\qquad\qquad\qquad\left.+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\right)\\ &=-n[x_kx_l]\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\\ &=[x_kx_l]\sum_{i=1}^n\left(2x_i\sum_{j=1}^n{x_j}\right)\\ &\,\,\color{blue}{=2} \end{align*}
... the linear terms ...
We obtain for $ 1\leq k\leq n$: \begin{align*} \color{blue}{[x_k]f_1(x_1,\ldots,x_n)}&=[x_k]\sum_{1\leq i<j\leq n}\left(\left(x_j-x_i\right)-\left(x_j-x_i\right)^2\right)\\ &=[x_k]\sum_{1\leq i<j\leq n}\left(x_j-x_i\right)\\ &=[x_k]\sum_{1\leq i<k}\left(x_k-x_i\right)+[x_k]\sum_{k<j\leq n}\left(x_j-x_k\right)\\ &=(k-1)-(n-k)\\ &\,\,\color{blue}{=2k-n-1}\\ \color{blue}{[x_k]f_2(x_1,\ldots,x_n)}&=[x_k]\left(\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\right)\\ &=[x_k]\left(-\sum_{i=1}^n{(n-2i+1)x_i}\right)\\ &\,\,\color{blue}{=2k-n-1}\\ \color{blue}{[x_k]f_3(x_1,\ldots,x_n)}&=[x_k]\left(-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\right.\\ &\qquad\qquad\qquad\left.+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\right)\\ &=-n[x_k]\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\\ &=-n[x_k]\sum_{i=1}^n\left(2x_i\cdot\frac{n-2i+1}{2n}\right)\\ &\qquad\qquad\qquad-n[x_k]\sum_{i=1}^n\left(-2\cdot\frac1n\sum_{j=1}^n{x_j}\cdot\frac{n-2i+1}{2n}\right)\\ &=-[x_k]\sum_{i=1}^nx_i(n-2i+1)+[x_k]\sum_{i=1}^n\frac{1}{n}\sum_{j=1}^n{x_j}(n-2i+1)\\ &=-(n-2k+1)+\sum_{i=1}^n\frac{1}{n}(n-2i+1)\\ &=-(n-2k+1)+(n+1-n-1)\\ &\,\,\color{blue}{=2k-n-1} \end{align*}
and finally the constant term .
We obtain \begin{align*} \color{blue}{[x_0]f_1(x_1,\ldots,x_n)}&=[x_0]\sum_{1\leq i<j\leq n}\left(\left(x_j-x_i\right)-\left(x_j-x_i\right)^2\right)\\ &\,\,\color{blue}{=0}\\ \color{blue}{[x_0]f_2(x_1,\ldots,x_n)}&=[x_0]\left(\left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)x_i}\right)\\ &\,\,\color{blue}{=0}\\ \color{blue}{[x_0]f_3(x_1,\ldots,x_n)}&=[x_0]\left(-n\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\right.\\ &\qquad\qquad\qquad\left.+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\right)\\ &=-n[x_0]\sum_{i=1}^n\left(x_i-\frac1n\sum_{j=1}^n{x_j}+\frac{n-2i+1}{2n}\right)^2\\ &\qquad\qquad\qquad+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\\ &=-n[x_0]\sum_{i=1}^n\left(\frac{n-2i+1}{2n}\right)^2+\frac1{4n}{\sum_{i=1}^n(n-2i+1)^2}\\ &\,\,\color{blue}{=0} \end{align*}
We observe the coefficients of terms with equal powers are equal.
Conclusion:
We obtain by collecting the results from above \begin{align*} \color{blue}{f_1(x_1,\ldots,x_n)}&\color{blue}{=f_2(x_1,\ldots,x_n)=f_3(x_1,\ldots,x_n)}\\ &\,\,\color{blue}{=(1-n)\sum_{i=1}^nx_i^2+2\sum_{1\leq i<j\leq n}x_ix_j+\sum_{i=1}^n(2i-n-1)x_i} \end{align*}
Taking a low tech approach, let our original summation be $\ s_n := u_n - t_n\ $ where $$ u_n := \sum_{1\le i<j\le n} (x_j-x_i), \quad t_n := \sum_{1\le i<j\le n} (x_j-x_i)^2. \tag{1}$$ Also, let $$ v_n := \sum_{1\le i\ne j\le n} x_i\ x_j = \left(\sum_{1\le k\le n} x_k \right)^2 - \sum_{1\le k\le n}x_k^2. \tag{2}$$ Now, $\;u_n = \sum_{i\le k\le n} c_{k,n}\ x_k\ $ where $$ c_{k,n} := (\sum_{1\le i\le k} 1) - (\sum_{k\le j\le n} 1) = k-(n-k+1) = 2k-n-1 \tag{3}$$ which counts how many times $\ k\ $ appears as $\ j\ $ minus the times it appears as $\ i\ $ in equation $(1).$ Thus, $$ u_n = \sum_{1\le k\le n} (2k-n-1)\ x_k = -\sum_{1\le k\le n} (n-2k+1)\ x_k . \tag{4}$$ Now, we get $\ t_n = \sum_{1\le i<j\le n} (x_j^2 + x_i^2 - 2x_jx_i)\ $ by expanding the square in equation $(1)$ and similarly to how we got equation $(3)$, we now get $$ t_n \!=\! \sum_{k=1}^n (k\!+\!(n\!-\!k\!+\!1)) x_k^2 +\! \sum_{1\le i\ne j\le n} x_ix_j \!=\! (n\!+\!1)\!\sum_{k=1}^n x_k^2\!+\! v_n. \tag{5}$$ Combining this with equation $(2)$ we get $$ t_n = n\sum_{1\le k\le n} x_k^2 - \sum_{1\le k\le n}x_k^2. \tag{6}$$ Combining this with equation $(4)$ we get $$ s_n = \left(\sum_{i=1}^n{x_i}\right)^2-n\sum_{i=1}^n{x_i^2}-\sum_{i=1}^n{(n-2i+1)\ x_i}, \tag{7}$$ which is the first identity requested.
Continuing, let $\ y_i = y_{i,n} := x_i -\frac1n\sum_{j=1}^n x_j.\ $ There is a famous formula in statistics $$ t_n = n \sum_{1\le i\le n} \Big(x_i-\frac1n\sum_{j=1}^n x_j\Big)^2 = n \sum_{1\le i\le n} y_i^2. \tag{8}$$ Notice that $$ \sum_{i=1}^n (n-2i+1) = 0. \tag{9}$$ Combining this with equation $(4)$ we get $$ u_n = -\sum_{1\le i\le n} (n-2i+1)\ y_i. \tag{10}$$ Combining this with equation $(8)$ we get $$ s_n = -n \sum_{i=1}^n y_i^2 -\sum_{1\le i\le n} (n-2i+1)\ y_i. \tag{11}$$ Continuing, let $\ z_i = z_{i,n} := y_{i,n} +\frac{n-2i+1}{2n}. \ $ Now $$ z_i^2 = y_i^2 + y_i\frac{n-2i+1}n + \frac{(n-2i+1)^2}{4n^2}. \tag{12}$$ Summing this over $\ i\ $ and multipling by $\ n\ $ gives us $$ n \sum_{i=1}^n z_i^2 \!=\! n \sum_{i=1}^n y_i^2 + \sum_{i=1}^n y_i(n\!-\!2i\!+\!1) \!+\! \frac1{4n}\sum_{i=1}^n (n\!-\!2i\!+\!1)^2. \tag{13}$$ Finally, combining equations $(11)$ and $(13)$ we get $$ s_n = - n \sum_{i=1}^n z_i^2 + \frac1{4n}\sum_{i=1}^n (n-2i+1)^2. \tag{14}$$ which is the second identity since $\ z_i = x_i -\frac1n\sum_{j=1}^n x_j +\frac{n-2i+1}{2n}.$
P.S. The identities and proofs are simplified if we use a non-standard indexing for the $\ x_i.\ $ So suppose we have an indexed set of $\ n\ $ numbers $\ \{x_{-n+1}, x_{-n+3}, \dots, x_{n-3}, x_{n-1}\}.\ $ For $\ n=0\ $ we have just $\{x_0\}.\ $ For $\ n=1\ $ we have the set $\ \{x_{-1}, x_1\}\ $ and so on. It is understood that we will sum from $\ -n+1\ $ to $\ n-1\ $ in steps of $2$. So define our new $$ u_n :=\! \sum_{-n+1\le i<j\le n-1} (x_j\!-\!x_i), \; t_n := \!\sum_{-n+1\le i<j\le n-1} (x_j\!-\!x_i)^2. \tag{15}$$ The first identity is now $$ s_n = u_n - t_n = \Big(\sum_i i\ x_i\Big) + \Big(\sum_i x_i\Big)^2 - n\Big(\sum_i x_i^2\Big). \tag{16}$$ The second identity is now $$ s_n = -n\ \sum_i \Big(x_i-\frac1n\sum_j x_j-\frac{i}{2n}\Big)^2 + \frac{n^2-1}{12}. \tag{17}$$