How to prove this identity nicely? 
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.
 A: 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!
A: $\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*}
A: 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!
A: 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}$$
