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

Question

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

Answer 1

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.

Answer 2

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.