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$.

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

2 Answers 2


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.


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.$$

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

You must log in to answer this question.