Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Do we assume each $a_i \ge 0$? – coffeemath Nov 11 '12 at 11:30
Use arithmetic and quadratic mean. – Berci Nov 11 '12 at 11:36
@Berci I thought this was usually the proof of the AM-QM inequality... – Arthur Nov 11 '12 at 11:44
@coffeemath. yes. we do. – user45099 Nov 11 '12 at 12:01
up vote 5 down vote accepted

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.

share|cite|improve this answer

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

share|cite|improve this answer
It's pretty clever and easy way!!! Great!!! – user45099 Nov 11 '12 at 23:02

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.