Arithmetic mean is less than geometric mean (Spivak Calculus 3rd Chapter 2 Problem 22) 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.
 A: The inequality $G_n\leq A_n $ is a simple application of Jensen's inequality using the concavity of the $\log$ function.
A: 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$.
A: Well, I found the corresponding question in my old Spivak, and I've got his "Supplement to Calculus" as well that contains all his answers.  It was question 20 from chapter 2 in my old edition.  Rather than convert it to LaTeX, I've taken the quicker route of posting images of the books!  In my edition the question was as follows:

and the following 3 images are his answer



Hope that helps :-).
A: There's a wikipedia article on this which contains several proofs, so take your pick :-).
A: Here is how I solved it, after trying out approaches similar to yours with no success for a few days I figured that it's probably easier to prove that  $\bar{G}_n^{(k+1)} \geq {G}_n^{(k)}$ than to prove  $\bar{G}_n^{(k)} \geq G_n$. I do not have any formal "training" in math so apologies is something is unclear.
We have:
$$\begin{array}{r@{ }c@{ }l}
A_n(a_1+a_2-A_n) &\geq& a_1 a_2 \\
0 &\geq& A_n^2 -A_n(a_1+a_2)+a_1 a_2 \\
0 &\geq& (A_n-a_1)(A_n-a_2)
\end{array}$$
This is true since $a_1 < A_n < a_2$.
We see that $a_1+a_2 = \bar{a}_1+\bar{a}_2$, so the arithmetic mean remains unchanged, so that we have $A_n=\bar{A}_n$. Now we can generalize this, let's say we have a set of $n$ elements $a_1, a_2, \ldots, a_n$ with a arithmetic mean $A_n$ and a geometric mean $G_n$. Let $\bar{G}_n^{(k)}$ be
\begin{equation*}
\bar{G}_n^{(k)} = \sqrt[n]{\prod_{i=1}^k \bar{a}_i \prod_{i=k+1}^n a_i}
\end{equation*}
Where $\bar{a}_1, \ldots, \bar{a}_{k-1}$ are equal to $A_n$ and $\bar{a}_k = \sum_{i=1}^k a_i - \sum_{i=1}^{k-1} \bar{a}_i$. So we actually have
\begin{equation*}
\bar{G}_n^{(k)} = \sqrt[n]{A_n^{k-1}  \left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right)\prod_{i=k+1}^n a_i}
\end{equation*}
It has already been proven that $\bar{G}_n^{(2)} \geq G_n$. Now we will show that $\bar{G}_n^{(k+1)} \geq {G}_n^{(k+1)}$. First we prove that if $\sum_{i=1}^k a_i > k A_n$ than there is at least one number in the set (we shall call it $a_{k+1}$)such that $ a_{k+1} < A_n$. If we assume that there is no such number, i.e. all $a_i > A_n$ for $i > k$ we have
$$\begin{array}{r@{ }c@{ }l}
\sum_{i=1}^k a_i + \sum_{i=k+1}^n a_i &>& k\cdot A_n +(n-k)A_n \\
\sum_{i=1}^n a_i &>& n \cdot A_n \\
\frac{\sum_{i=1}^n a_i}{n} &>& A_n 
\end{array}$$
which is a contradiction. The inequality also holds with the inequality signs reversed. So now we can say that if $\sum_{i=1}^k a_i > k A_n$ we choose such a number from the set so that $a_{k+1} < A_n$ (and vice versa) and if $\sum_{i=1}^k a_i = k A_n$ we choose any remaining number from the set. We obtain
$$\begin{array}{r@{ }c@{ }l}
A_n^{k} \left(\sum_{i=1}^{k+1} a_i - \sum_{i=1}^{k}\bar{a}_i\right)\prod_{i=k+2}^n a_i &\geq& A_n^{k-1}  \left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right) \prod_{i=k+1}^n a_i \\
A_n\left(\sum_{i=1}^{k} a_i - \sum_{i=1}^{k-1}\bar{a}_i+a_{k+1}-A_n\right) &\geq& a_{k+1} \left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right) \\
\end{array}$$
$$\begin{array}{r@{ }c@{ }l}
A_n (a_{k+1}-A_n)+A_n\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right)- a_{k+1} \left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right) &\geq& 0 \\
A_n (a_{k+1}-A_n) +(A_n-a_{k+1})\left(\sum_{i=1}^k a_i - \sum_{i=1}^{k-1}\bar{a}_i\right) &\geq& 0 \\
(A_n-a_{k+1})\left(\sum_{i=1}^k a_i - k\cdot A_n \right) &\geq& 0
\end{array}$$
We can see, according to the property of $a_{k+1}$, that both terms in the parentheses have the same sign (or one of them is 0), so the inequality is proven.  $\bar{G}_n^{(n)}$ is  equal to $A_n$, so the chain of inequalities looks like
\begin{equation*}
A_n = \bar{A}_n = \bar{G}_n^{(n)} \geq \bar{G}_n^{(n-1)} \geq \bar{G}_n^{(n-2)} \geq \ldots \geq \bar{G}_n^{(2)} \geq G_n
\end{equation*}
which proves that $A_n \geq G_n$.
