Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
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.$$
