1
$\begingroup$

Prove the following:

The summation ranges from 1 to n.

${\sum{a_i^2}\ge \frac1n }$ provided $\sum a_i$=1.

without using the method used to prove chebyshev's inequality.

I can do this very easily assuming that we can arrange $a_i$ such that $a_1\ge$$a_2\ge$...$\ge a_n$. but I want to do it without using it.

I derive two conditions but cannot continue from there:

further work:

${\sum{a_i^2} }\le$$\sum a_i\sum a_i$$\implies \sum{a_i^2}\le 1$

and $n=\sum\sum a_i$.

$\endgroup$
  • 3
    $\begingroup$ Do we assume each $a_i \ge 0$? $\endgroup$ – coffeemath Nov 11 '12 at 11:30
  • 2
    $\begingroup$ Use arithmetic and quadratic mean. $\endgroup$ – Berci Nov 11 '12 at 11:36
  • $\begingroup$ @Berci I thought this was usually the proof of the AM-QM inequality... $\endgroup$ – Arthur Nov 11 '12 at 11:44
  • $\begingroup$ @coffeemath. yes. we do. $\endgroup$ – user45099 Nov 11 '12 at 12:01
5
$\begingroup$

Assume the $a_i$ are positive and sum up to $1$. Then we have $$ 1=\left(\sum_{i=1}^n a_i\right)\cdot \left(\sum_{j=1}^n a_j\right) = \left(\sum_{i=1}^n\sum_{j=1}^n a_i a_j\right) \leq \sum_{i=1}^nna_i^2 $$ where the last inequality is motivated by greed.

By greed I mean the following: Given any two different indices $i \neq j$, the product $a_ia_j$ appears twice in $\left(\sum_{i=1}^n\sum_{j=1}^n a_i a_j\right)$. But we have that $2a_ia_j \leq a_i^2 + a_j^2$, so making that switch for any pair of unequal indices, we get the last inequality. Dividing by $n$ then gives the result you want.

PS. It is called greed because there's an interpretation of the rearrangement inequality, where you let one sequence be denomination of coins and the other how many of each coin you take. The last inequality above is just a special case of the rearrangement inequality where the two sequences are equal.

$\endgroup$
2
$\begingroup$

The result also follows from the Cauchy-Schwarz inequality, for which: $$\sum_{i=1}^{n}a_i = \sum_{i=1}^{n}a_i\cdot 1 \leq \sqrt{\sum_{i=1}^n a_i^2}\cdot\sqrt{\sum_{i=1}^n 1},$$ or: $$\frac{1}{n}\left(\sum_{i=1}^{n}a_i\right)^2\leq \sum_{i=1}^{n} a_i^2.$$

$\endgroup$
  • $\begingroup$ It's pretty clever and easy way!!! Great!!! $\endgroup$ – user45099 Nov 11 '12 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy