kompliziert Ungleichung und Gleichung

Question

Given n > 2 and reals $x_1 \leq x_2 \leq $ ... $ \leq x_n$, show that $(\sum _{i,j} \vert x_i - x_j \vert)^2 \leq \dfrac{2}{3} (n^2 -1)\sum _{i,j} (x_i - x_j)^2$ . Show that we have equality if the sequence is an arithmetic progression. \\

EDIT(Lu): Gemeint ist zuerst $$x_1 \leq x_2 \leq ... \leq x_n$$

und dann: $$(\sum _{i,j} \vert x_i - x_j \vert)^2 \leq \dfrac{2}{3} (n^2 -1)\sum _{i,j} (x_i - x_j)^2$$ 

vgl. Kommentar jd139.

Comments

Given \(n > 2\) and reals \(x_1 \leq x_2 \leq \ldots \leq x_n\), show that 
$$\left(\sum _{i,\,j} \left| x_i - x_j \right|\right)^2 \leq \frac{2}{3} \left(n^2 -1\right)\sum _{i,\,j} \left(x_i - x_j\right)^2.$$Show that we have equality if the sequence is an arithmetic progression.

---

Staunte gerade über die zwei Wörter für "Folge" im gleichen Satz. 

"Folge (sequence) ist "arithmetische Folge (progression)"  ?

offenbar ja: Vgl. https://en.wikipedia.org/wiki/Arithmetic_progression

Answer 1

Hi, erst mal der Fall, wenn \( x_i \) eine arithmetische Folge ist mit \( x_{i+1} - x_i = \Delta \). Dann gilt folgendes

$$ (1) \quad \left[  \sum_{i,j=1}^n \left| x_i - x_j \right|  \right]^2 = \left[  2 \Delta \sum_{i=1}^{n-1} \sum_{j=1}^{n-i} j \right]^2 = \frac{ \Delta^2 n^2 (n^2 - 1)^2 }{9} $$

Und es gilt

$$ (2) \quad \sum_{i,j=1}^n \left( x_i - x_j \right)^2 = 2 \Delta^2 \sum_{i=1}^{n-1} \sum_{j=1}^{n-i} j^2 = \frac{ \Delta^2 n^2 (n^2-1) }{6} $$

Aus (2) folgt durch Multiplikation mit \(  \frac{2}{3}\left(  n^2-1 \right) \), dass die beiden Ausdrücke (1) und (2) gleich sind.

Für nicht arithmetische Folgen schreib ich heute Abend was, jetzt ist es zu heiss und ich geh schwimmen.

Comments

Hi,
beide Seiten der Ungleichung sind translations invariant, d.h. ich kann \( x_i \) durch \( x_i - a \) ersetzen, und die linke und rechte Seite der Ungleichung ändert sich nicht. Wählt man $$ a = \frac{1}{n} \sum_{i=1}^n x_i $$ dann folgt $$ \sum_{i=1}^n (x_i - a) = 0 $$
D.h. man kann o.B.d.A annehmen das \( \sum_{i=1}^n x_i = 0 \) gilt.

Die Differenzen \( | x_i - x_j  | \) sind symmetrisch und für \( i = j \) gleich \( 0 \), und \( x_j > x_i \) für \( j > i \) deshalb gilt

$$ (1) \quad \sum_{i,j=1}^n | x_i - x_j | = 2\sum_{i \lt j} (x_j - x_i) = 2\sum_{i=1}^n (2i-n-1) x_i $$
Mit der Cauchy-Schwarzen Ungleichung folgt
$$ (2) \quad \left(  \sum_{i,j=1}^n | x_i - x_j | \right)^2 \le 4 \sum_{i=1}^n (2i-n-1)^2 \sum_{i=1}^n x_i^2 = \frac{4}{3} n(n^2-1) \sum_{i=1}^n x_i^2 $$

Für die rechte Seite gilt
$$ (3) \quad \sum_{i,j=1}^n (x_i - x_j)^2 = n\sum_{i=1}^n x_i^2 -2\sum_{i=1}^n x_i \sum_{j=1}^n x_j + n\sum_{j=1}^n x_j^2 = 2n\sum_{i=1}^n x_i^2  $$

wegen \( \sum_{i=1}^n x_i = 0 \)

also gilt

$$ (4) \quad \sum_{i=1}^n x_i^2 = \frac{1}{2n} \sum_{i,j=1}^n (x_i - x_j)^2  $$
Jetzt (4) in (2) einsetzten und fertig.