If $a_1, \ldots, a_n \ge 0$, the arithmetic mean $$A_n={a_1 + \cdots + a_n \over n}$$ and the geometric mean $$G_n = \sqrt[n]{a_1 \cdots a_n}$$ satisfy $G_n \le A_n$.
As a first step to prove this inequality, the author suggests to suppose $a_1 \lt A_n$; then some $a_i$ satisfies $a_i \gt A_n$, so we suppose $a_2 \gt A_n$.
Let $\overline a_1 = A_n$ and $\overline a_2 = a_1 + a_2 – \overline a_1$.
The first question of the exercise is to prove that $\overline a_1 \overline a_2 \ge a_1 a_2$.
This is easy enough because it's the same as proving that $A_n^2 -(a_1+a_2)A_n + a_1a_2 \le 0$, that is $(A_n – a_1)(A_n – a_2) \le 0$, which is true because $(A_n – a_1) \gt 0$ and $(A_n – a_2) \lt 0$.
The next question is to explain why repeating this process eventually proves that $G_n \lt A_n$.
Let $\overline G_n$ and $\overline A_n$ be the geometric and arithmetic means obtained by replacing $a_1$ and $a_2$ with $\overline a_1$ and $\overline a_2$.
From the inequality just proved, it's $\overline G_n \ge G_n$; moreover, $\overline A_n = A_n$, so being able to prove $\overline G_n \le A_n$ would also prove $G_n \le A_n$.
I can easily see that replacing every $a_i$ with $A_n$, the geometrical mean would equal $A_n$, but I've not been able to prove formally by induction that continuing to replace $a_i$ with $A_n$ keep the resulting geometric mean $\le G_n$.
I thought it would be necessary to ensure that the arithmetic mean is unchanged; so I would expect it to be $\overline a_i = A_n$ for $i=1,\ldots,k \lt n$ and $\overline a_{k+1} = [(a_1 + \ldots + a_{k+1}) – (\overline a_1 + \ldots + \overline a_k)]$.
The first inequality that was proved is the case $k=1$, but I'm having difficulties in understanding how to:
- Prove that the inequality holds for $k=l+1$ if it holds for $k=l$
- Justify the case $k=n$, because $a_{n+1}$ would appear in the expression
Here's a sketch of the proof for 1. that I failed to complete; if the inequality holds for $k=l$, then $$A_n^l(\sum_{i=1}^l a_i – \sum_{i=1}^{l-1} \overline a_i) – \prod_{i=1}^l a_i \ge 0.$$
Then for $k=l+1$ the inequality is written $$A_n^{l+1}(\sum_{i=1}^{l+1} a_i – \sum_{i=1}^{l} \overline a_i) – \prod_{i=1}^{l+1} a_i \ge 0$$ that is, noting that $\overline a_l = A_n$, $$A_nA_n^l(\sum_{i=1}^l a_i – \sum_{i=1}^{l-1} \overline a_i) + A_n^{l+1}a_{l+1} – A_n^{l+2} – a_{l+1}\prod_{i=1}^{l} a_i \ge 0.$$
Now, if $a_{l+1} = A_n$, we get the expression for $k=l$; if $a_{l+1} \gt A_n$, then the inequality holds if the following holds $\overline a_l = A_n$, $$A_nA_n^l(\sum_{i=1}^l a_i – \sum_{i=1}^{l-1} \overline a_i) + A_n^{l+2} – A_n^{l+2} – a_{l+1}\prod_{i=1}^{l} a_i \ge 0,$$ that is $$A_nA_n^l(\sum_{i=1}^l a_i – \sum_{i=1}^{l-1} \overline a_i) – a_{l+1}\prod_{i=1}^{l} a_i \ge 0,$$ but I've not been able to complete the proof.
Also, I can't find a way to write the case $k=n$.
Thanks for your attention and assistance.
Best Answer
Let $A$ be the arithmetic mean (called $A_n$ in the question), and call a number $a_i$ unbalanced if $a_i \neq A$.
The arithmetic mean of the unbalanced elements is $A$ at all times during the execution of the algorithm. This makes every step of the process convert at least one unbalanced element to $A$, so that the number of unbalanced is eventually reduced to zero. Each step increases the product $a_1 a_2 \dots a_n$.