The following was a puzzle presented to Marshwood GT students on March 1, 2019. Have fun doing math!

It is well known that the \(\log\) function is concave. In other words, for any real number \(0 \leq \lambda \leq 1\) and any positive numbers \(x,y\):

$$\log(\lambda x+(1-\lambda)y) \geq \lambda \log(x)+(1-\lambda)\log(y) \ (1)$$For example, if we let \(\lambda=\frac{1}{2}\), then we find that:

$$\log\left(\frac{x+y}{2}\right)\geq \frac{\log(x)+\log(y)}{2} \ (2)$$On the other hand, if we let \(\lambda=\frac{1}{3}\), we get:

$$\log\left(\frac{x+2y}{3}\right) \geq \frac{1}{3}\log(x)+\frac{2}{3}\log(y) \ (3)$$As you can see, the fact that \(\log\) is concave is very powerful, because it can help prove a lot of different inequalities. Now, use the fact that \(\log\) is concave to prove the AM-GM inequality: For any group of \(n\) positive numbers \(a_1, a_2, ..., a_n\), the following holds true:

$$\frac{a_1+a_2+...+a_n}{n} \geq \sqrt[n]{a_1a_2...a_n} \ (4)$$**Part 0:** Use logarithms to show that AM-GM inequality is equivalent to the following:

From here on, we will focus on the proving inequality \((5)\) rather than the actual AM-GM inequality because they are equivalent, so proving inequality \((5)\) is the same as proving AM-GM inequality.

Inequality \((5)\) is also commonly known as the finite-form of Jensen's inequality.

**Part 1:** First, let's focus on a small value of \(n\): If \(n=2\), then the inequality becomes:

Plug in \(\lambda=\frac{1}{2}\) into inequality \((1)\) to prove inequality \((6)\).

**Part 2:** Now, let's make things a bit harder: If \(n=3\), then the inequality becomes:

Now, if we plug in \(x=a_1\) and \(y=\frac{a_2+a_3}{2}\) into inequality \((3)\), we get:

$$\log\left(\frac{a_1+a_2+a_3}{3}\right)\geq \frac{1}{3}\log(x)+\frac{2}{3}\log\left(\frac{a_2+a_3}{2}\right) \ (8)$$Combine inequalities \((6)\) and \((8)\) in order to prove inequality \((7)\).

**Part 3:** Finally, let's try one more example: If \(n=4\), then the inequality becomes:

Now, the key thing to realize here is that:

$$\frac{a_1+a_2+a_3+a_4}{4}=\frac{1}{4}a_1+\frac{3}{4}\frac{a_2+a_3+a_4}{3}$$Therefore, if we plug in \(\lambda=\frac{1}{4}, x=a_1, y=\frac{a_2+a_3+a_4}{3}\) into inequality \((1)\), we get:

$$\log\left(\frac{a_1+a_2+a_3+a_4}{4}\right)\geq \frac{1}{4}\log(a_1)+\frac{3}{4}\log\left(\frac{a_2+a_3+a_4}{3}\right) \ (10)$$Combine inequalities \((7)\) and \((10)\) in order to prove inequality \((9)\).

**Part 4:** Hopefully, you realize the pattern by now: In order to prove the inequality for \(n=k\), you need to use the inequality for \(n=k-1\). This is a really powerful technique called mathematical induction, and it allows us to prove AM-GM inequality for all positive integers \(n\). First, we state that the inequality is true for \(n=k-1\), assuming that it has already been proven:

Then, we use this inequality to prove the inequality for \(n=k\). To be clear, the inequality for \(n=k\) is the following:

$$\log\left(\frac{a_1+a_2+...+a_k}{k}\right)\geq \frac{\log(a_1)+\log(a_2)+...+\log(a_k)}{k} \ (12)$$Now, just like in Part 3, a key thing to notice is that:

$$\frac{a_1+a_2+...+a_k}{k}=\frac{1}{k}a_1+\frac{k-1}{k}\frac{a_2+a_3+...+a_k}{k-1}$$Thus, if we plug in \(\lambda=\frac{1}{k}, x=a_1, y=\frac{a_2+a_3+...+a_k}{k-1}\) into inequality \((1)\), we get:

$$\log\left(\frac{a_1+a_2+...+a_k}{k}\right)\geq \frac{1}{k}\log(a_1)+\frac{k-1}{k}\log\left(\frac{a_2+a_3+...+a_k}{k-1}\right) \ (13)$$Combine inequalities \((11)\) and \((13)\) to prove inequality \((12)\).

After proving inequality \((12)\), we can finish off our whole proof: By induction, since the AM-GM inequality for \(n=k-1\) implies the AM-GM inequality for \(n=k\), the AM-GM inequality must be true for all positive integers \(n\). Q.E.D.