# I don't understand this proof of the AM-GM inequality?

The proof uses this lemma which I understand:

$\mathbf {Lemma}$: Suppose $x$ and $y$ are positive real numbers such that $x>y$. If we decrease $x$ and increase $y$ by some positive quantity $E$ such that $x-E \ge y+E$, then $(x-E)(y+E) \gt xy$ . $\;$Hence, by subtracting $E$ from $x$ and adding it to $y$, we leave the average of the two numbers unchanged while increasing their product.

$\mathbf {Proof}:$ Suppose $a_{1}, a_{2}, a_{3}... a_{n}$ are positive real numbers with average $A$ and product $P$. If all $a_{i}$ are equal, then both the geometric mean and the arithmetic mean are equal to $A$. Let $a_{j}$ be one number closest to $A$ without being equal to $A$. Without loss of generality, let $a_{j} \lt A$ . Since the average of the numbers is $A$, there is at least one member of the set greater than $A$. Let $a_{k}$ be the greatest of these numbers. Clearly we must have $a_{k}-A \gt A-a_{j}$ since $a_j$ is closer to $A$ than any other $a_i$ not equal to $A$. We now use our lemma. Replace $a_j$ with $A$ and $a_k$ with $a_k-(A-a_j)$ . Note that $a_k-(A-a_j) \ge a_j +(A-a_j)$ , so we can apply our lemma with $(A-a_j)$ as our $E$ . By our lemma, the average of the numbers in the new set is the same, but the product is now higher. If we continue this process, we make one of the members of the set equal to $A$ with each application of the process. Hence, in some finite number of steps, we will make all the numbers equal to $A$. Thus, we prove that of all the sets of positive numbers with average $A$, the set with maximum product has all the elements equal to $A$.

$1)$ I don't understand why they don't loose generality when they say to let $a_j$ be the number closest to $A$ and let $a_j \lt A$. It certainly is possible for this not to be the case, for example the set ${2, 10, 10, 10}$. The average is $8$, but the number closest to $A$ is greater than $A$, so I don't see how the proof can apply to this set.

$2)$ I don't see how this process makes makes the elements of the set equal to $A$. If you want $a_j+E$ and $a_k-E$ to be equal to $A$, then $a_j$ and $a_k$ have to be equidistant from $A$.

$3)$ if you do bring one pair of terms at a time equal to $A$, then that means you must have an equal number of therms below and above $A$.

Any help is appreciated, thanks!

• 1) They mean a similar strategy works if $a_j > A$. 2) One of the terms is changed to $A$ (since $a_j + E = A$), but that's all the progress that is needed. Jun 16 '13 at 20:53

1) You are correct, there needs to be some tweaking.

2) It makes one more number equal to A, so by induction eventually they all will be.

3) You don't make both equal to A; you make at least one equal to A.

Perhaps a simpler proof of the middle part, avoiding the first issue, is this: Let $a,b$ be chosen so that $a<A<b$; if this is not possible then all the $a_i$'s are already equal. Set $c=\min(|A-b|,|A-a|$). We replace $a$ by $a+c$ and $b$ by $b-c$. By the same calculation as in the lemma, the average remains the same and the product increases. We have now made at least one of $a,b$ equal to $A$. Continue until all $a_i=A$.

• Ok thanks I think I got it
– Ovi
Jun 16 '13 at 20:59

1) I'd suggest to choose any indices $j,k$ with $a_j<A<a_k$ (which exist unless all $a_i$ are equal) and let $E=\min\{a_k-A,A-a_j\}$ in the lemma.

2) $E$ is specifically chosen so that at least one of $a_j+E$, $a_k-E$ equals $A$. The text explicitly makes $a_j=A$, i.e. chooses $E=A-a_j$, and decreases $a_k$ accordingly (I do similar in my suggestion for$1)$). It is enough to make only one of these equal to $A$ in order to increase the count.

3) You can only be sure to have at least one bigger and at least one smaller number. Only in the last step you are sure to "accidentally" bring two numbers at once to the average $A$ (because it is not possible that all numbers but one are equal to $A$).

The proof that uses the Lemma is rather hard-going. For my perspective on the proof see my answer to the related question; it also answers your question, I think.

I gather that the AM-GM inequality you are talking about is $\,(a_1\cdots a_n)^{1/n}\leq(a_1+\cdots+a_n)/n\,$ for positive real numbers $a_1$, $\ldots$, $a_n$. There is a slightly more general AM-GM inequality:

Let $n\geq 1$ be an integer, let $a_1,\ldots,a_n>0$, and let $\lambda_1,\ldots,\lambda_n> 0$ satisfy $\lambda_1+\cdots+\lambda_n=1$. Then $a_1^{\lambda_1}\cdots a_n^{\lambda_n}\leq\lambda_1a_1+\cdots\lambda_na_n$, where the equality holds if and only if $a_1=\cdots=a_n$.

I will give my favorite proof of the generalized AM-GM inequality. The embarassing thing about this particular proof is that I cannot remember whether I have seen it somewhere or I hacked it up myself when I was fooling around thinking up different ways (some of them extremely weird) of proving the inequality. In case you have come across this proof, or its close relative, somewhere, anywhere, please let me know by giving the reference in a comment to the present answer.
(Yes, I know the proof by Pólya, I know the Jensen's inequality, I know that the AM-GM inequality is a manifestation of the concavity of the $\log$ function.)

All we need for the proof of the generalized AM-GM inequality is the following inequality:$\newcommand{\RR}{\mathbb{R}}$

For every $x\in\RR$, $x>0$, we have $\,x-1\geq\ln x\,$, where the equality holds iff $\,x=1$.

The proof is simple: setting $f(x):=x-1-\ln x$ we have $f(1)=0$, and $f'(x)=1-x^{-1}$ is (strictly) negative for $0<x<1$ and is (strictly) positive for $x>1$.

Proof of the generalized AM-GM inequality. $~$For every $x>0$ we have \begin{aligned} (xa_1)^{\lambda_1}\cdots(xa_n)^{\lambda_n} ~&\:=\: x\cdot a_1^{\lambda_1}\cdots a_n^{\lambda_n}~, \\[1ex] \lambda_1(xa_1)+\cdots+\lambda_n(xa_n) ~&\:=\: x\cdot(\lambda_1a_1+\cdots\lambda_na_n)~. \end{aligned} This means that it suffices to prove the inequality with $xa_1$, $\ldots$, $xa_n$ in place of $a_1$, $\ldots$, $a_n$ for any $x>0$ we choose. We choose $x=(a_1^{\lambda_1}\cdots a_n^{\lambda_n})^{-1}\!$, that is, we can assume that $a_1^{\lambda_1}\cdots a_n^{\lambda_n}=1$ and have to prove that then $1\leq \lambda_1a_1+\cdots+\lambda_na_n$. But this is easy: \begin{aligned} \lambda_1a_1+\cdots+\lambda_na_n-1 ~&\:=\: \lambda_1(a_1-1) + \cdots +\lambda_n(a_n-1) \\[.5ex] ~&\:\geq\: \lambda_1\ln a_1 + \cdots + \lambda_n\ln a_n \\[.5ex] ~&\:=\: 0~, \end{aligned} where the equality holds iff $a_1=\cdots=a_n=1$.$~$ Done.