11
$\begingroup$

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:

  1. Prove that the inequality holds for $k=l+1$ if it holds for $k=l$
  2. 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.

$\endgroup$
1
  • $\begingroup$ Do you think you ever figured the induction proof that Spivak is looking for? $\endgroup$
    – Eric Auld
    Apr 12, 2014 at 22:49

5 Answers 5

4
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This is the intuitive approach I'm trying to formalize. Just replacing an element with $A$ does not ensure that the arithmetic mean of the unbalanced elements is $A$ and that $a_1 a_2 \cdots a_n$ is increased (e.g. if we take $6,1,5$, $A=4$; if we replace the first element with $A$, we also have to replace the second element with $6 + 1 - 4 = 3$ to keep $A = 4$, to keep the arithmetic mean of the unbalanced elements $A$, and to increase $a_1 a_2 \cdots a_n$). I'm trying to prove by induction that these manipulations indeed do increase $a_1 a_2 \cdots a_n$ (I can add a sketch of the proof). $\endgroup$ May 7, 2013 at 20:36
  • $\begingroup$ The inductive thing you want to prove is that in a set of $k$ unbalanced elements with mean $A$, replacing two of them (by the given process) does not change the mean, and increases the product. Then, remove the values of $A$ just created, and continue. $\endgroup$
    – zyx
    May 7, 2013 at 20:39
  • $\begingroup$ Thanks for your comment; as you can see from my edit, I was trying a different approach by replacing $k$ elements. I'm curious about a way to complete the proof I was trying to give, but your suggestion looks way more viable :) $\endgroup$ May 7, 2013 at 21:26
4
$\begingroup$

The inequality $G_n\leq A_n $ is a simple application of Jensen's inequality using the concavity of the $\log$ function.

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, however I've been explicitly asked for an inductive proof based on replacing $a_i$ with $A_n$. I found a somehow similar approach in proving this inequality is used in Hardy's A Course of Pure Mathematics, but the complete proof is not given. $\endgroup$ May 7, 2013 at 19:37
3
$\begingroup$

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:

image of spivak book

and the following 3 images are his answer

1st image of spivak supplement to calculus

2nd image of spivak supplement to calculus

3rd image of spivak supplement to calculus

Hope that helps :-).

$\endgroup$
6
  • $\begingroup$ Thanks for your contribution :) I'm probably nitpicking, but this procedure is slightly different because two elements are replaced by their arithmetic mean, while I'm replacing one of them with the arithmetic mean of the entire set and "adjusting" another element accordingly. I'm also trying to find a more formal way to express "enough" times (i.e. to prove that after at most $n$ repetitions $\overline G_n = A_n$). $\endgroup$ May 7, 2013 at 23:18
  • 4
    $\begingroup$ Spivak's answer to (a) with averaging of pairs is incorrect. If you start with $a < b < c$ and first replace the smaller two, then the larger two, by pair averages, then this process can be repeated without converging (in a finite number of steps, as Spivak asserts) to a triple of equal values. In the limit you get the correct inequality but there is no finite chain from $G_n$ to $A_n$ by this method. $\endgroup$
    – zyx
    May 9, 2013 at 0:07
  • $\begingroup$ ... but the scans are great memorabilia. Typewriters! "Old Spivak"! Thanks for posting that. $\endgroup$
    – zyx
    May 9, 2013 at 0:25
  • $\begingroup$ the images no longer work....... $\endgroup$
    – user153330
    Apr 7, 2015 at 15:45
  • $\begingroup$ @user153330 Images still look fine to me in google chrome on windows 7! $\endgroup$ Jul 6, 2015 at 22:01
2
$\begingroup$

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. Thus, 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 get $$\begin{array}{r@{ }c@{ }l} A_n^{k} \left(\sum_{i=1}^{k+1} a_i - k A_n\right)\prod_{i=k+2}^n a_i &\geq& A_n^{k-1} \left(\sum_{i=1}^k a_i - (k-1)A_n\right) \prod_{i=k+1}^n a_i \\ A_n\left(\sum_{i=1}^{k+1} a_i - k A_n\right) &\geq& a_{k+1} \left(\sum_{i=1}^k a_i - (k-1)A_n\right) \\ \end{array}$$ $$\begin{array}{r@{ }c@{ }l} A_n (a_{k+1}-A_n)+A_n\left(\sum_{i=1}^k a_i - (k-1)A_n\right)- a_{k+1} \left(\sum_{i=1}^k a_i - (k-1)A_n\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$.

$\endgroup$
1
$\begingroup$

There's a wikipedia article on this which contains several proofs, so take your pick :-).

$\endgroup$
2
  • $\begingroup$ I've already looked at them, and as a mathematical illiterate I found the one credited to Cauchy to be really interesting :) However, the problem explicitly asks to prove the inequality by induction via replacement of the elements $a_i$ with $A_n$. As I stated in another comment, this problem is probably inspired to an example from Hardy's A Course of Pure Mathematics, where the elements $a_i$ are replaced with $G_n$; however, only the case $n=2$ is treated. My question is about formal generalization of this approach to the proof. $\endgroup$ May 7, 2013 at 19:51
  • $\begingroup$ OK, I've now posted Spivak's answer to his question :-). Hope that helps! $\endgroup$ May 7, 2013 at 23:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .