We can rewrite the given expression as \( \sum_i (2i-n-1)x_i \)^2 \leq (n^2 - 1)/3 \( n\sum x_i^2 - (\sum x_i )^2\). As the expression is translation invariant (obvious from the original form), we can assume that \sum x_i =0. The rest follows by Cauchy-Schwartz.

The crucial idea is that we may assume that Sum x_k = 0. I had tried to solve this problem, but I did not succeed. I came up with the first identity in Jayanta's message, but I was not smart enough to make his clever assumption. Let me complete the proof (a) Since sum_{i,j} |x_j x_i|= 2 sum_{i<j} (x_j x_i) and sum_{i,j} (x_j x_i)^2 = 2 sum{i<j} (x_j x_i)^2 , it suffices to show that ( sum_{i<j} (x_j x_i) )^2 <= [(n^2-1)/3] sum{i<j} (x_j x_i)^2. Since sum_{i<j} (x_j x_i)^2 = n sum x_i^2 (sum x_i )2 , and assuming that sum x_i =0, it suffices to show that ( sum_{i<j} (x_j x_i) )^2 <= [n(n^2-1)/3] sum x_i^2 We observe that (*) sum_{i<j} (x_j x_i)= (n-1) x_n +(n-3) x_{n-1} +-(n-3)x_2-(n-1) x_1=sum a_k x_k, where a_{n-k} = n-1-2k, for k=1,,,n. Note that if n=2m, then sum a_k^2 = 2(1^2+3^2++(2m-1)^2 ) = 2m(2m-1)(2m+1)/3 = n(n^2-1)/3, and if n=2m-1, then a_{n-k} = 2(m-k), for k=1,,n (note that a_m=0), so sum a_k^2 =8[(1^2+2^2++(m-1)^2] = 8(m-1)m(2m-1)/6 = n(n^2-1)/3, since m(m-1)=(n^2-1)/4. Thus, by Cauchy's inequality we have, ( sum_{i<j| (x_j x_i) )2 <= (sum a_k^2 ) (sum x_k^2 ) ={ n(n^2-1)/3}(sum x_k^2 ), as desired. Comment: To see (*), consider the following triangle x_n-x_1 x_{n-1}-x_1 x_3-x_1 x_2-x_1 x_n-x_2 x_{n-1}-x_2 x_3-x_2 x_{n-1}-x_{n-2} x_n-x_{n-2} x_n-x_{n-1} (b) We have quality of if and only if x_k= 0 for all k, or a_k= t*x_k for all k and some nonzero real number t. In the first case clearly we have an arithmetic progression. In the second case, since 2 = a_k-a_{k-1} = t(x_k-x_{k-1}), we have x_k = x_{k-1} + 2/t, and the result follows.

well, I meant "Since sum_{i<j} (x_j x_i)^2 = n sum x_i^2 (sum x_i )^2 , and assuming that sum x_i =0, .....e.t.c"

this one was a rather cute problem.but two people have beaten me agen b4 i cud post my solution.and my proof is same as achilleas proof(u guys are fast) which wud u ppl rate as the best question at this year's imo(i luvd no2)

Question: Is the following inequality true? Let n>2 and x_1 <=x_2<=...<=x_n and y_1<=y_2<=...<=y_n. Then (sum_{i,j} |x_i-x_j|) * (sum_{i,j} |y_i-y_j|) <= 2(n^2-1)/3 sum_{i,j} |x_i-x_j)(y_i-y_j)| . This would be a generalization of the IMO problem. We could assume that sum x_k=sum y_k=0 and use the identity n*(sum x_k * y_k) = (sum x_k)*(sum y_k) + sum_{i<j} (x_i-x_j)(y_i-y_j). Then it would suffice to show that (sum_{i<j} (x_j-x_j)) * (sum_{i<j} (y_j-y_i) ) <= [2n(n^2-1)/3] sum x_k * y_k Since sum_{i<j} (x_j-x_i)) = sum a_k * x_k and sum_{i<j} (y_j-y_i)) = sum a_k * y_k, where a_k are as above for k=1,2,..,n-1 (I had written up to n inadvertently in my previous message). Also sum (a_k)^2=2n(n^2-1)/3 (proof in my previous message) and sum_{i<j} (x_j-x_j)) * (sum_{i<j} (y_j-y_i) ) =(sum a_k * x_k) * (sum a_k * y_k) but I cannot see how this would prove it; it seems like a deadend. Any other approach? (Of course, the inequality could be false)

let a_k=x_{k+1}-x_k>=0, then the rhs (except the (n^2-1)/3 factor) is [a_1^2+a_2^2...+a_{n-1}^2 + (a_1+a_2)^2+(a_2+a_3)^2+...+(a_{n-2}+a_{n-1})^2+ ... +(a_1+a_2+...+a_{n-1})^2] write a k-sum square as (a_{i+1}+...+a_{i+k})^2 as k^2 [(a_{i+1}+...+a_{i+k})/k]^2, so altogether we have (n-1)*1^2+(n-2)*2^2+...+1*(n-1)^2 terms, then use the power mean inequality to get it cheers,

Elinor, I hope this is the way you did it.. The number of terms is (n-1)*1^2+(n-2)*2^2+...+1*(n-1)^2 = sum (n-k)*k^2 for k=1,2,...,n-1 = n^2(n^2-1)/12. So the rhs of the reduced inequality (i.e. the sum for i<j) times the numer of terms n^2(n^2-1)/12 is larger than or equal to the square of the sum S=(a_1+...+a_{n-1} +2*(a_1+a_2) + 2*(a_2+a_3)+...+2*(a_{n-2}+a_{n-1})+..+(n-1)*(a_1+....+a_{n-1})) (This also follows from Cauchy-Scwartz). In order to finish the proof we need to show that S>= (n/2)*S' , where S' is the sum=(a_1+...+a_{n-1} + (a_1+a_2) + (a_2+a_3)+...+(a_{n-2}+a_{n-1})+..+(a_1+....+a_{n-1})) In order to do this we observe that after making the operations in the two sums we see that for k=1,2,..,n-1, the coefficient of a_k in S is nk(n-k)/2 and in S' is k(n-k). (of course, this needs proof!!) Thus we actually have equality S= (n/2)*S' , and the result follows.

Achilleas Sinefakopoulos wrote: Question: Is the following inequality true? Let n>2 and x_1 <=x_2<=...<=x_n and y_1<=y_2<=...<=y_n. Then (sum_{i,j} |x_i-x_j|) * (sum_{i,j} |y_i-y_j|) <= 2(n^2-1)/3 sum_{i,j} |x_i-x_j)(y_i-y_j)| . ...(Of course, the inequality could be false) It is false in general, (as will be shown later). This can also be easily seen by trying n=3. However under certain restrictions for the x_i, y_i the attack given by Elinor and Achilles can work by replacing the Cauchy-Schwartz (or AM-RMS) inequality with Chebyshev's inequality. However this gives the very awkward restriction that if f(i, j) = |x_i-x_j|/|i-j| and g(i,j) = |y_i-y_j|/|i-j|, f(i, j)<f(k,l) iff g(i, j)<g(k,l). I can't think of any interesting pairs of sequences that satisfy this condition, other than y_i = x_i + ki for k in R. Also, there is a corresponding inequality using the other form of Chebyshev if f(i, j)<f(k,l) iff g(i, j)>g(k,l), showing that the originally proposed inequality is in general false.

Alison, thanks for your reply!

Lemma: $\sum_{i,j=1}^n |x_i - x_j| |i - j| = \frac{n \sum_{i,j=1} |x_i - x_j|}{2}$. Proof: Let $a_1 = x_1$, and let $a_{i} = x_i - x_{i-1}$ for all $i$ with $2 \leq i \leq n$. The lemma we wish to prove can easily be seen to be equivalent to $\sum_{1 \leq i < j \leq n} (i - j)(a_{i+1} + a_{i+2} + \cdots + a_j) = \frac{n}{2} \sum_{1 \leq i < j \leq n} (a_{i+1} + a_{i+2} + \cdots + a_j).$ When expanded, both sides are a linear combination of $a_1, a_2, \cdots, a_n$. We will determine the coefficients of each variable on both sides of the equation. On the left-hand side, $a_k$ appears if and only if $i+1 \leq k \leq j$, in which case it comes with a factor if $(j-i)$. Hence, the coefficient of $a_k$ on the left-hand side is $\sum_{i=1}^{k-1} \sum_{j=k}^n (j-i) = \frac{n(k-1)(n-k+1)}{2}$. On the right-hand side, $a_k$ appears iff $i+1 \leq k \leq j$, in which case it comes with a factor if $\frac{n}{2}$. Hence, the coefficient of $a_k$ on the right-hand side is $\frac{n(k-1)(n-k+1)}{2}$, which is equal to the coefficient on the left. $\blacksquare$ It can easily be seen that $\sum_{i=1}^n \sum_{j=1}^n |i - j|^2 = \frac{2(n^2-1)}{3} \cdot \frac{n^2}{4}$. By the Cauchy-Schwarz inequality, \begin{align*} \frac{2(n^2 - 1)}{3} \left( \sum_{i,j=1}^n |x_i - x_j|^2 \right) &= \frac{\left( \sum_{i,j=1}^n |x_i - x_j|^2 \right) \left( \sum_{j=1}^n |i-j|^2 \right)}{\frac{n^2}{4}} \\ &\geq \left (\frac{ \sum_{i,j=1}^n |x_i - x_j| \, |i - j| }{ \frac{n}{2} } \right)^2 \\ &= \left( \sum_{i,j=1}^n |x_i - x_j| \right)^2, \end{align*} as desired. The cases of equality easily follow from the above application of Cauchy-Schwarz.

I have known that this problem can be solved using Cauchy-Schwarz inequality, but even with this information I haven't known how to solve it. It can be solved by using derivatives in a very simple way. Just compute derivatives on each variable and it can be easily seen that $x_2-x_1=x_3-x_2$ and so on.

We first make use of symmetry to rewrite the inequality as \[\left(\sum_{1\le i<j\le n}|x_i-x_j|\right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}|x_i-x_j|^2\right)\]. WLOG that $x_1\le x_2\le\dots\le x_n$ and let $x_{i-1}-x_i=a_i$. The inequality is equivalent to \[\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)^2\right)\] for all $a_1,\dots,a_{n-1}$. But this can be rewritten as \[\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\] By Cauchy-Schwarz: \begin{align*} \left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l^2\right)&\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l\left(a_i+\dots+a_j\right)\right)^2\\ &=\left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2 \end{align*} We claim that \[\sum_{j-i=l}(a_i+\dots+a_j)=\sum_{j-i=(n-l)}(a_i+\dots+a_j)\]. Indeed, we may consider the $l\times(n-l)$ matrix: \[ \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_l \\ a_2 & a_3 & \dots & a_{l+1} \\ \vdots & \vdots & \ddots & \vdots\\ a_{n-l} & a_{n-l+1} & \dots & a_n \end{array} \right)\] The first sum corresponds to summing the matrix row by row, and the second corresponds to summing it column by column. Thus the two sums are equal, as claimed. Hence: \begin{align*} \left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2&=\left(\sum_{l=1}^{n-1}\frac n2\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\\ &=\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2 \end{align*} We may also check that \[\sum_{l=1}^{n-1}\sum_{j-i=l}l^2=\sum_{l=1}^{n-1}(n-l)l^2=\frac{n^4-n^2}{12}\]. Thus we have proven that \[\frac{n^4-n^2}{12}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\] Dividing $\frac{n^2}4$ yields \[\frac{n^2-1}{3}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\] as desired. Furthermore, from Cauchy's equality condition, equality holds if and only if $a_1=a_2=\dots=a_{n-1}$ - that is, when the $x_i$ form an arithmetic sequence.

This is a very old inequality and there are a number of elegant solutions but I would like to contribute with a very straightforward approach using induction and derivatives. For $n=3$, the inequality is obviously true. Now let's assume that the inequality is true for $n$ and we will prove it for $n+1$. Let's define $y_{i}$ such that $y_{i}=x_{i}-\frac{\sum_{j=1}^{n}x_{j}}{n}$ and we have $\sum_{i=1}^{n} y_{i}=0$ We need to prove that for $y_{n+1} \geq y_{n}$ we have: $P(y_{n+1}) \geq 0$ where: \[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(\sum_{i,j=1}^{n+1} (y_{i}-y_{j})^2) - (\sum_{i,j=1}^{n+1} |y_{i}-y_{j}|)^2 \geq 0\]Let $A_{n} = \sum_{i,j=1}^{n} (y_{i}-y_{j})^2$ and $B_{n} = \sum_{i,j=1}^{n} |y_{i}-y_{j}|$ and we have from induction's hypothesis $\frac{2}{3}(n^2-1)A_{n} \geq B_{n}^2 $. After Simplification, we get: \[P(y_{n+1}) = \frac{2}{3}((n+1)^2-1)(2ny_{n+1}^2+\frac{n+1}{n}A_{n})-(2ny_{n+1}+B_{n})^2\]$P$ reaches a minimal value for $y_{n+1}$ such that $P'(y_{n+1})=0$ and after simplification, we get: \[P'(y_{n+1})=0 \Leftrightarrow y_{n+1}=\frac{3B_{n}}{2n(n-1)}\]Then we have: \[P(y_{n+1}) \geq P(\frac{3B_{n}}{2n(n-1)})=\frac{n+2}{n-1}(\frac{2}{3}(n^2-1)A_{n}-B_{n}^2) \geq 0\]Equality case: we have $\frac{2}{3}(n^2-1)A_{n}-B_{n}^2 = 0$ which is true only if there exists a real number $r$ such that $x_{i}=ir$ for all $i\leq n$, and \[x_{n+1}=y_{n+1}+\frac{\sum_{i=1}^{n} x_{i}}{n}=\frac{3\sum_{i,j=1}^{n}|i-j|r}{2n(n-1)}+\frac{\sum_{i=1}^{n} ir}{n}=\frac{(n+1)r}{2}+\frac{(n+1)r}{2}=(n+1)r\]Which completes the proof by induction.

basically the same as first cauchy sol WLOG let $x_1\le x_2\le \cdots \le x_n$, then we work on the LHS, \begin{align*} \sum_{i=1}^n \sum_{j=1}^n |x_i-x_j| &=\sum_{i=1}^n \left(\sum_{j=1}^{i-1}(x_i-x_j)+\sum_{j=i+1}^{n}(x_j-x_i)\right)\\ &=\sum_{i=1}^n(2i-n-1)x_i+\sum_{i=1}^n \left(\sum_{j=i+1}^{n}x_j-\sum_{j=1}^{i-1}x_j\right)\\ &=2\sum_{i=1}^n(2i-n-1)x_i. \end{align*}Now we work on the RHS, \begin{align*} \sum_{i=1}^n \sum_{j=1}^n |x_i-x_j|^2 &=\sum_{i=1}^n\sum_{j=1}^n (x_i^2+x_j^2)-2\sum_{i=1}^n\sum_{j=1}^n x_ix_j\\ &=2n\sum_{i=1}^n x_i^2-2\left(\sum_{i=1}^n x_i\right)^2.\\ \end{align*} The key idea is that the original inequality does not depend on $\sum_{i=1}^n x_i$, so we may set it equal to zero. Then the desired inequality becomes \[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\frac{n(n^2-1)}{3}\sum_{i=1}^n x_i^2.\] Applying C-S on the LHS, we have \[\left(\sum_{i=1}^n(2i-n-1)x_i\right)^2\le\left(\sum_{i=1}^n (2i-n-1)^2\right)\left(\sum_{i=1}^n x_i^2\right),\]so it suffices to show that \[\sum_{i=1}^n (2i-n-1)^2=\frac{n(n^2-1)}{3}.\] If $n=2m$, we have \begin{align*} \sum_{i=1}^n (2i-n-1)^2 &= 2(1^2+3^2+\cdots+(2m-1)^2)\\ &=2\sum_{i=1}^{m}\left(\binom{2i-1}{2}+\binom{2i}{2}\right)\\ &=2\binom{2m+1}{3}\\ &=\frac{n(n^2-1)}{3}, \end{align*}as desired. If $n=2m+1$, we have \begin{align*} \sum_{i=1}^n (2i-n-1)^2 &= 2(2^2+\cdots+(2m)^2)\\ &=2\sum_{i=1}^{m}\left(\binom{2i}{2}+\binom{2i+1}{2}\right)\\ &=2\binom{2m+2}{3}\\ &=\frac{n(n^2-1)}{3}, \end{align*}as desired. The equality case occurs at \[x_1:x_2:\cdots:x_n=1-n:3-n:\cdots:n-1,\]so they are in arithmetic progression, as desired.

This would have been a really nice inequality problem if the question hadn't stated the inequality case. Anyway, posting this for storage, basically the same CS solution as others. We'll first rewrite the sum condition as \[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le \frac{n^2 - 1}{3} \sum_{1 \le i < j \le n} (x_j - x_i)^2 \]Now, we'll prove that \[ \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} = \frac{n^2}{12} \]This can be proved by noticing that \begin{align*} \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} &= \frac{1}{n^2} \sum_{1 \le i <j \le n} (j - i)^2 \\ &= \frac{1}{n^2} \sum_{k = 1}^{n-1} k^2 (n - k) \\ &= \frac{1}{n} \sum_{k = 1}^{n-1} k^2 - \frac{1}{n^2} \sum_{k = 1}^{n-1} k^3 \\ &= \frac{1}{n} \left( \frac{1}{6} (n-1)(n)(2n-1) \right) - \frac{1}{n^2} \left( \frac{(n-1)n}{2} \right)^2 \\ &= \frac{(n-1)(2n-1)}{6} - \frac{(n-1)^2}{4} \\ &= \frac{2(2n^2 - 3n + 1) - 3(n^2 - 2n + 1)}{12} \\ &= \frac{n^2 - 1}{12} \end{align*}which is what we wanted. Therefore, we could rewrite the condition as \[ \left( \sum_{1 \le i < j \le n} (x_j - x_i) \right)^2 \le 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \]Now, apply CS at the RHS, we have \[ 4 \left( \sum_{1 \le i < j \le n} \frac{(j - i)^2}{n^2} \right) \left( \sum_{1 \le i < j \le n} (x_j - x_i)^2 \right) \ge \left( 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) \right)^2 \]It suffices to prove that \[ 2 \sum_{1 \le i < j \le n} \frac{j - i}{n} (x_j - x_i) = \sum_{1 \le i < j \le n} (x_j - x_i) \]But this is true by considering each coefficient of $x_i$. Notice that in the RHS, the coefficient of $x_j$ is $( j - 1) - (n - j) = 2j - n - 1$ and in the LHS, we have the coefficient of $x_j$ is \[ \frac{2 ( (1 + 2 + \dots + j - 1) - (1 + \dots + (n - j)) )}{n} = \frac{(j - 1)j - (n -j)(n-j+1)}{n} = \frac{2nj - n^2 - n}{n} = 2j - n - 1\]

Let $L$ and $R$ equal the LHS and RHS of the inequality respectively. We have $R = \frac{4(n^2-1)}{3}\sum_{i>j\ge1}^{n}(x_i-x_j)^2$ since $(x_i-x_j)^2 = (x_j-x_i)^2$. Next, let $J = \sum_{i>j\ge1}^{n}(x_i-x_j)^2$ and $K = \sum_{i = 1}^n\sum_{i \ge j \ge 1}^nx_j^2$. Also, let $c_n = \binom{n}{2}, c_{n-1} = \binom{n}{2}-n, \ldots c_1 = \binom{n}{2}-(n-1)n = -\binom{n}{2}$. By Cauchy-Schwarz, $$JK = \left((x_2-x_1)^2+(x_3-x_1)^2+(x_3-x_2)^2+\ldots+(x_n^2-x_{n-1}^2)\right)\left((1^2)+(2^2+1^2)+(3^2+\ldots+2^2+1^2)\right)$$$$\ge \left(1(x_2-x_1)+2(x_3-x_1)+1(x_3-x_2)+\ldots+2(x_n-x_{n-2})+1(x_n-x_{n-1})\right)^2$$$$= \left(c_nx_n+c_{n-1}x_{n-1}+c_{n-2}x_{n-2}+\ldots+c_1x_1\right)^2 = I^2$$where the last step can be proven by considering specific values of $x_i$. Next, I will find the specific value of $K$. We have the following lemmas: $\sum_{i = 1}^ni^3 = \frac{n^2(n+1)^2}{4}, \sum_{i = 1}^ni^2 = \frac{n(n+1)(2n+1)}{6}, \sum_{i = 1}^ni = \frac{n(n+1)}{2}.$ Therefore, $$K = \sum_{i = 1}^{n-1} \frac{i(i+1)(2i+1)}{6} = \sum_{i = 1}^n \frac{2i^3+3i^2+i}{6} = \frac{\frac{(n-1)^2n^2}{2}+\frac{(n-1)n(2n-1)}{2}+\frac{(n-1)n}{2}}{6} = \frac{(n-1)n^2(n+1)}{12}.$$Therefore, we have $$R = \frac{4(n^2-1)}{3K}JK \ge \frac{4(n-1)(n+1)}{\frac{3(n-1)n^2(n+1)}{12}}I^2 = \frac{16}{n^2}I^2.$$ Finally, it suffices to prove $L = \frac{16}{n^2}I^2$. Note that $L = 4\left(\sum_{i \ge 1 \ge 1}|x_i-x_j|\right)^2$. Also, let $d_i = 2i-(n+1)$. For specific $x_p$, notice that if $i > p$, then $|x_i-x_p|$ will result in a negative $x_p$ term. If $i < p$, then $|x_p-x_i|$ will result in a positive $x_p$ term, and otherwise nothing. We now see that the coefficient of $x_p$ will be $$\left((p-1)-1+1\right)-\left(n-(p+1)+1)\right) = 2p-n-1$$as desired. However, $\frac{nd_i}{2} = pn-\frac{n^2}{2}-\frac{n}{2} = \binom{n}{2}-n(n-p) = xc_i$. This means $L = 4\left(\frac{2}{n}\right)^2I^2 = \frac{16}{n^2}I^2$, which proves the inequality. Finally, we see that equality holds when $\frac{|x_i-x_j|}{|i-j|}$ is a constant which gives equality in the Cauchy-Schwarz. Since $i < j \implies x_i < x_j$, this means $x_1, x_2, \ldots x_n$ must be an arithmetic sequence. $\blacksquare$ Remarks: If this problem did not tell you the equality condition, it would be quite harder because you have to guess it, which makes the Cauchy-Schwarz part much more contrived. I actually enjoyed bashing this problem unlike some other problems I did.

Shift so that \(\sum_{i=1}^nx_i=0\). By Cauchy-Schwarz, \[ \left[\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{n(n+1)(n-1)}{12}\cdot\sum_{i=1}^nx_i^2;\]that is, \[\left[4\sum_{i=1}^n\left(i-\frac{n+1}2\right)x_i\right]^2 \le\frac{2(n^2-1)}3\left[2n\sum_{i=1}^nx_i^2-2\left(\sum_{i=1}^nx_i\right)^2\right],\]which is equivalent to the desired inequality. Equality holds iff \(x_1\), \ldots, \(x_n\) is an arithmetic sequence.

Since shifting the sequence $(x_1,x_2,\dots, x_n)$ does not affect the problem, we can assume that the sum is $0$. We have \begin{align*}\left(\sum_{i,j=1}^{n}|x_i-x_j|\right)^2 &=\left(2\sum_{1\le i\le j\le n}(x_j-x_i)\right)^2 \\ &= \left((2n-2)x_n+(2n-6)x_{n-1}+\dots +(2-2n)x_1\right)^2 \\ &\le ((2n-2)^2+(2n-6)^2+(2n-10)^2+\dots + (2-2n)^2)(x_1^2+x_2^2+\dots + x_n^2) \\ &= \frac{4(n-1)(n)(n+1)}{3}(x_1^2+x_2^2+\dots + x_n^2) \\ &= \frac{2(n^2-1)}{3}\cdot 2(nx_1^2 + nx_2^2 + \dots + nx_n^2) \\ &= \frac{2(n^2-1)}{3}\cdot 2\left((n-1)\left(\sum_{i=1}^{n}{x_i^2}\right) + \left(\sum_{i=1}^{n}{x_i}\right)^2 - 2\sum_{1\le i<j\le n}x_ix_j\right) \\ &= \frac{2(n^2-1)}{3}\cdot 2\left(\sum_{1\le i<j\le n}(x_i-x_j)^2\right) \\ &= \frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}(x_i-x_j)^2 \end{align*}Clearly, the equality condition of Cauchy will force the equality case of this inequality to also be an arithmetic sequence. In the case that one of the coefficients in the second line of our work is zero, we can add $\varepsilon$ to each of the coefficients to get the same inequality but avoid division by zero.

Induction led me to a solution that is way too long, but I’d recommend you to try it if you couldn’t find the Cauchy-Schwarz way (like me) We will do induction on $n$. The base case $n = 1$ simplifies to $0 \le 0$, which is clear. For the inductive step, we will assume that the problem is true for $n = k$, and prove that it is also true for $n = k + 1$. Noticing that the problem statement does not change if we shift all variables $x_i$ by a constant, assume that their sum $\sum_{i = 1}^k x_i = 0$ to simplify calculations. Let \[\rho_1 = \sum_{i, j=1}^k |x_i - x_j| \text{ and } \rho_2 = \sum_{i,j = 1}^k (x_i - x_j)^2.\]By the inductive hypothesis, we may assume that \[\frac{2(k^2 - 1)}{3} \cdot \rho_2 \ge \rho_1^2.\]Let $P(x_{k + 1})$ be \[P(x_{k + 1}) = \frac{2[(k + 1)^2 - 1]}{3} \cdot \sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 - \left(\sum_{i,j = 1}^{k + 1}|x_i - x_j|\right)^2.\]We wish to show that $P(x_{k + 1}) \ge 0$ for $x_{k + 1} \ge x_k$. Using the fact that $\sum_{i = 1}^k x_i = 0$, we can calculate \[\sum_{i,j = 1}^{k + 1} |x_i - x_j| = p_1 + 2 \sum_{i = 1}^{k} (x_{k + 1} - x_i) = p_1 + 2kx_{k + 1}.\]We can also calculate \[\sum_{i,j = 1}^{k + 1}(x_i - x_j)^2 = \rho_2 + 2\sum_{i = 1}^k (x_i - x_{k + 1})^2 = p_2 + 2\sum_{i = 1}^k x_i^2 + 2k x_{k + 1}^2.\]In addition, I claim that \[2\sum_{i = 1}^k x_i^2 = \frac{\rho_2}{k}.\]This is because \begin{align*} \rho_2 &= \sum_{i,j = 1}^k (x_i - x_j)^2 \\ &= 2k \sum_{i = 1}^k x_i^2 - 2\sum_{i,j = 1}^k x_i x_j \\ &= 2k \sum_{i = 1}^k x_i^2 - 2 \left(\sum_{i = 1}^k x_i\right)\left(\sum_{j = 1}^k x_j\right) \\ &= 2k \sum_{i = 1}^k x_i^2. \end{align*}So, we can further simplify our formula to get \[\sum_{i,j = 1}^{k + 1} (x_i - x_j)^2 = \frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2.\]Thus, \[P(x_{k + 1}) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + 2kx_{k + 1}^2\right) - (\rho_1 + 2k x_{k + 1})^2.\]Treating this as a quadratic polynomial in terms of $x_{k + 1}$ holding all other terms are constant, $P(x_{k + 1})$ is minimized at \[x_{k + 1} = \frac{-(-4k\rho_1)}{2\left(\frac{4k^3 + 8k^2}{3} - 4k^2\right)} = \frac{4k\rho_1}{2\left(\frac{4k^3 - 4k^2}{3}\right)} = \frac{3\rho_1}{2k(k - 1)}.\]Plugging this in, \[P\left(\frac{3\rho_1}{2k(k - 1)}\right) = \frac{2k^2 + 4k}{3} \cdot \left(\frac{k + 1}{k} \cdot \rho_2 + \frac{9\rho_1^2}{2k(k - 1)^2}\right) - \left(\rho_1 + \frac{3\rho_1}{k - 1}\right)^2.\]This simplifies to \begin{align*} P(x_{k + 1}) &= \frac{2(k + 2)(k + 1)}{3} \cdot \rho_2 + \left(\frac{3(k + 2)}{(k - 1)^2} - \frac{(k + 2)^2}{(k - 1)^2}\right)\rho_1^2 \\ &= \frac{k + 2}{k - 1}\left(\frac{2(k^2 - 1)}{3}\rho_2 - \rho_1^2\right). \end{align*}By the inductive hypothesis, $\frac{2(k^2 - 1)}{3}\rho_2 \ge \rho_1^2$, so we get that $P(x_{k + 1}) \ge 0$ which completes the inductive step. Equality holds if and only if for all $0 \le k \le n - 1$, \[x_{k + 1} = \frac{3\sum_{i,j = 1}^k |x_i - x_j|}{2k(k - 1)}.\]We will prove that this is equivalent to $x_1, x_2, \ldots, x_n$ being an arithmetic sequence using induction. For $n = 2$, the problem statement becomes $4(x_2 - x_1)^2 \le 4(x_2 - x_1)^2$, which is true for all $x_1$ and $x_2$. Since any two numbers are in an arithmetic sequence, the base case is clear. For the inductive step, assume that $d = x_2 - x_1 = x_3 - x_2 = \cdots = x_k - x_{k - 1}$, and we will prove that $x_{k + 1} - x_k = d$ as well. This is equivalent to the numbers being in an arithmetic sequence. Since we previously assumed that $x_1 + x_2 + \cdots + x_k = 0$, this means that $x_k = \frac{(k - 1)d}{2}$. We can simplify \begin{align*} x_{k + 1} &= \frac{3 \sum_{i,j = 1}^k |x_i - x_j|}{2k(k - 1)} \\ &= \frac{3 \sum_{1 \le i < j \le k} d(j - i)}{k(k - 1)}. \end{align*}In the sum in the numerator, a difference of $d$ occurs $n - 1$ times, a difference of $2d$ occurs $n - 2$ times, and so-on. Thus, \begin{align*} x_{k + 1} &= \frac{3d}{(k - 1)k}((k - 1) \cdot 1 + (k - 2) \cdot 2 + \cdots + 1 \cdot (k - 1)) \\ &= \frac{3d}{(k - 1)k} \sum_{i = 1}^{k - 1} i(k - i) \\ &= \frac{3d}{(k - 1)k} \left(k\sum_{i = 1}^{k - 1} i - \sum_{i = 1}^{k - 1} i^2 \right) \\ &= \frac{3d}{(k - 1)k} \left(k \cdot \frac{(k - 1)k}{2} - \frac{(k - 1)k(2k - 1}{6}\right) \\ &= 3d \left(\frac{k}{2} - \frac{2k - 1}{6}\right) \\ &= d\left(\frac{k + 1}{2}\right). \end{align*}Thus, $x_{k + 1} - x_k = d$, completing the inductive step. Thus, we have proven the inequality and have shown that equality holds if and only if the variables are in an arithmetic sequence.

Divide both sides by $4$ and only consider the case when $i<j$. Let $a_i=x_{i+1}-x_i$. Then the second summation becomes, $$\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_i+a_{i+1}+\dots+a_j)^2$$Since equality occurs when $a_1=a_2=\dots=a_{n-1}$ we apply the Cauchy Schwartz inequality in the form $$(\frac{n}{2}\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_i+a_{i+1}+\dots+a_j))^2\leq(\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_i+a_{i+1}+\dots+a_j)^2)(\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(i-j)^2)$$$$(\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_i+a_{i+1}+\dots+a_j))^2\leq \frac{n^2-1}{3}\sum_{i=1}^{n-1}\sum_{j=i}^{n-1}(a_i+a_{i+1}+\dots+a_j)^2$$

So we need to prove that $$F(a_1,a_2,\dots,a_{n-1}):=\sum_{k=1}^{n-1} \left [ k(n-k)(n^2-1)-3k^2(n-k)^2\right ]a_k^2 -\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} \left [ 3ij(n-i)(n-j)-i(n^2-1)(n-j)\right ] 2a_ia_j\geqslant 0 \qquad (1)$$The inequality is homogeneous, so we can assume wlog that $$a_1+\dots+a_{n-1}=1\qquad (2)$$So that the domain of $F$ becomes $[0,1]^{n-1}$ which is compact. So $F$ attains a global minimum. First, suppose $\{a_1,\dots,a_{n-1}\}\subset \{0,1\}$. If one of the $a_i$'s is $1$ and the rest are $0$, then $F>0$ because $k(n-k)(n^2-1)-3k^2(n-k)^2>0$ is true when $1\leq k<n$. And when all are $0$ then obviously $F=0$. Now suppose $a_1,\dots,a_{n-1}\in (0,1)$ so that we can proceed with Lagrange Multipliers. Taking the gradients of $F$ and the constraint function $a_1+\dots+a_{n-1}$ we get the equations \begin{align*} & 2(k(n-k)(n^2-1)-3k^2(n-k)^2)a_k-2\sum_{i=1}^{k-1} (3ik(n-i)(n-k)-i(n^2-1)(n-k))a_i \\ & \qquad -2\sum_{j=k+1}^{n-1} (3kj(n-k)(n-j)-k(n^2-1)(n-j))a_j=\lambda, \quad (k=1,2,\dots, n-1) \qquad (3)\end{align*}(Take the empty sum to be $0$). Notice that we have $n$ variables $\lambda,a_1,\dots,a_{n-1}$ and $n$ linear independent (this is not very hard to see?) equations $(2)$ and $(3)$. So if there is a solution, it must be unique. We claim the solution is $$a_1=a_2=\dots=a_{n-1}=\frac{1}{n-1}, \quad \lambda=0.$$Indeed this solution satisfies $(2)$ and we can show without much effort that $$\sum_{i=1}^{k-1} (3ik(n-i)(n-k)-i(n^2-1)(n-k))+\sum_{j=k+1}^{n-1} (3kj(n-k)(n-j)-k(n^2-1)(n-j))=k(n-k)(n^2-1)-3k^2(n-k)^2 \qquad (4)$$so it also satisfies $(3)$. Finally, showing $F\left (\frac{1}{n-1},\frac{1}{n-1},\dots,\frac{1}{n-1}\right)=0$ is pretty much the same as proving $(4)$, so we'll omit this too. Thus the global minimum of $F$ is $0$. This proves $(1)$ and so the original inequality as well. Also the equality holds iff $a_1=\dots=a_{n-1}$, as seen above. This implies that the equality case of the original inequality is when $x_1, \dots, x_n$ is arithmetic. This finishes the problem.