Prove $\left(\sum_{1 \le i Question:

Let $x_1,\, x_2,\,\ldots,\, x_n$ be real numbers. Prove that $$\left(\sum_{1 \le i <j \le n} |x_i-x_j|\right)^2 \ge (n-1)\sum_{1\le i<j \le n} (x_i-x_j)^2.$$

This problem is different 2003 IMO Shortlist  problem. see:
http://www.artofproblemsolving.com/Forum/viewtopic.php?p=265&sid=fd9e67731e5084a02adb9974cf035c51#p265
also can see this official solution page 17::http://pdf.znate.ru/view/1335/1
for this we have
we can assume that without loss of generality that
$$\sum_{i=0}^{n}x_{i}=0$$
then we have
$$\sum_{i,j=1}^{n}(x_{i}-x_{j})^2=n\sum_{i=1}^{n}x^2_{i}-\sum_{i=1}^{n}x_{i}\sum_{j=1}^{n}x_{j}+n\sum_{j=1}^{n}x^2_{j}=2n\sum_{i=1}^{n}x^2_{i}?$$
$$\sum_{i,j=1}^{n}|x_{i}-x_{j}|=2\sum_{i<j}(x_{j}-x_{i})=2\sum_{i=1}^{n}(2i-n-1)x_{i}?$$
then I can't use these result to  solve my problem.(maybe these result not true,because my problem don't have $x_{1}\le x_{2}<\cdots<x_{n}$).
and other idea: when $n=3$,then 
$$\Longleftrightarrow (|a-b|+|b-c|+|a-c|)^2\ge 2[(a-b)^2+(b-c)^2+(a-c)^2]$$
let
$$|a-b|=x,|b-c|=y,|c-a|=z$$
$$(x+y+z)^2\ge 2(x^2+y^2+z^2)\Longleftrightarrow 2xy+2yz+2zx\ge x^2+y^2+z^2?$$
Thank you for you help
 A: I show below that the intuition in Ivan’s partial answer does lead to a complete solution.
As in Ivan’s answer, I assume without loss that
$x_1 \leq x_2 \leq \ldots \leq x_n$, and I put $y_j=x_j-x_{j-1}$ for any
$j\geq 2$ (but I do not assume $\sum_{j}x_j=0$, contrary to Ivan). Then all the $y_j$ are nonnegative and 
we have $x_k=x_1+\sum_{j=2}^k y_j$ for every $k$. The LHS can then
be rewritten as $L$ where
$$
L=\bigg(\sum_{k=2}^n (k-1)^2(n+1-k)^2y_k^2\bigg)+
\bigg(\sum_{2 \leq i,j \leq n}^n 2(i-1)(j-1)(n+1-i)(n+1-j)y_iy_j\bigg)
$$
Similarly, the RHS can be rewritten as $(n-1)R$ where
$$
R=\bigg(\sum_{k=2}^n (k-1)(n+1-k)^2y_k^2\bigg)+
\bigg(\sum_{2 \leq i,j \leq n}^n 2(i-1)(n+1-j)y_iy_j\bigg)
$$
The quantity that we are trying to control is then $D=L-(n-1)R$ ; but $D$ can
be written as 
$$
D=\bigg(\sum_{k=2}^n a_ky_k^2\bigg)+
\bigg(\sum_{2 \leq i,j \leq n}^n b_{ij}y_iy_j\bigg)
$$
where 
$$
a_k=(k-1)(n+1-k)\big((k-1)(n+1-k)-(n-1)\big)=
(k-1)(n+1-k)(k-2)(n-k) \geq  0 
$$
and
$$
\begin{array}{lcl}
b_{i,j}&=& 2(i-1)(n+1-j)\big((j-1)(n+1-i)-(n-1)\big) \\
 &\geq & 2(i-1)(n+1-j)\big(i(n+1-i)-(n-1)\big) \\
 &= & 2(i-1)(n+1-j)\big((i-2)(n-1-i)+(n-1)\big) \geq 0
\end{array}
$$
This finishes the proof.
A: An idea only. Assuming $x_1<x_2<...<x_n$ I would suggest the following substitution: $$x_i\to \sum _{i=1}^{k}y_i$$ where $y_i>0$ for all $i\geq 2$. Due to the assumption that  $\sum _{i=1}^{n}x_i=0$ we have $$y_1=\frac{-\sum _{i=2}^{i=n}(n+1-i)y_i}{n}$$
The inequality is equivalent to the following function being positive: $$f(n)=\left(\sum_{i=1}^{n}(2i-n-1)x_i\right)^2-n(n-1)\left(\sum _{i=1}^{n}{x_i}^2\right)$$
Using the above substitutions ($y_i$ and then $y_1$) and simplifying for the first few values of $n$ we have:$$
\begin{align}
    f(3) &= 4 y_2 y_3
\\ f(4) &= 4 \left(3 y_2 y_3+y_3^2+3 y_2 y_4+3 y_3 y_4\right)
\\ f(5) &= 4 \left(6 y_2 y_3+3 y_3^2+8 y_2 y_4+10 y_3 y_4+3 y_4^2+6 y_2 y_5+8 y_3 y_5+6 y_4 y_5\right)
\end{align}
$$
et cetera...
I've checked the first few values of $n$ and it seems the resulting polynomials have only positive coefficients, meaning they are positive because we assumed $y_i>0$.
If one can work out the values of the coefficients or at least show by induction that they are increasing it would solve the problem.
