# Prove the following inequality

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. - 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 ## 2 Answers 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.$\$

-
It's pretty clever and easy way!!! Great!!! –  user45099 Nov 11 '12 at 23:02