Proof of the Arithmetic Mean - Geometric Mean Inequality

We will prove the Arithmetic Mean-Geometric Mean Inequality using a proof method called Forward-Backward Induction.

To outline the proof, in the forward argument, we will show that the statement is true for larger and larger values of \( n\) (specifically for all \(n\) powers of \(2\)). In the backward argument, we will show that if the statement is true for \(n\) variables, then it is also true for \( n-1\) variables. By combining these arguments, we show that the statement is true for any value of \( n\), by first applying the forward argument to show that it is true for a power of 2 that is larger than \(n\), and then using the backward argument to show that it is true for \( n\).

Arithmetic Mean - Geometric Mean Inequality

AM-GM inequality: For \( n\) non-negative real values \( x_1, x_2, \ldots x_n \),

\[ \displaystyle \frac { \displaystyle \sum_{i=1}^n x_i} {n} \geq \sqrt[n] { \prod_{i=1}^n x_i } .\]

Proof: (Forward) We will show this by induction. The base case \( 2^1=2\) is proved in Complete the Square. For the induction step, suppose the statement is true for some \( 2^k\); we would like to show that the statement is true for \( 2^{k+1}\). Given \( \{a_i\}_{i=1} ^{2^{k+1}}\) positive real values, we divide the set in half (obtaining \( \{a_i\}_{i=1} ^{2^{k}}\) and \( \{a_i\}_{i=2^k+1} ^{2^{k+1}}\)), and then apply the induction hypothesis to each set.

\[ \begin{aligned}{} \frac{a_1+a_2+\ldots+a_{2^{k+1}}}{2^{k+1}} = & \frac {1}{2}\left( \frac{a_1+a_2+\ldots a_{2^k}}{2^k} + \frac {a_{2^k +1} + a_{2^k+2} + \ldots a_{2^{k+1}} } {2^k} \right)\\ \geq & \frac {1}{2} \left( \sqrt[2^k] {a_1 \cdot a_2 \cdots a_{2^k} } + \sqrt[2^k] {a_{2^k+1} \cdot a_{2^k+2} \cdots a_{2^{k+1} } } \right) \\ \geq & \sqrt[2^{k+1}] {a_1 \cdot a_2 \cdots a_{2^k} \cdot a_{2^k+1} \cdot a_{2^k+2} \cdots a_{2^{k+1}} }\\ \end{aligned} \]

The first inequality follows from using the Induction Hypothesis twice, while the second inequality follows from the 2-variable case, by setting \( x_1 = a_1 \cdot a_2 \cdots a_{2^k}\) and \( x_2 = a_{2^k+1} \cdot a_{2^k+2} \cdots a_{2^{k+1}} \). This completes the argument for the forward step.

(Backward) We will now show that if the statement is true for \( k\), then it is also true for \( k-1\). Assume that the statement is true for any set of \( k\) positive real values, i.e. that

\[ \frac { x_1 + x_2 + \ldots + x_k } {k} \geq \sqrt[k]{ x_1 \times x_2 \times \cdots \times x_k}. \]

Then, it will be true for the k variables

\[ x_1=a_1, x_2=a_2,\ldots x_{k-1} = a_{k-1} \text{ and } x_k = \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1}, \]

implying

\[ \begin{aligned} & \frac { a_1 + a_2 + \ldots +a_{k-1} + \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} } {k} \geq \sqrt[k]{ a_1 \times a_2 \times \cdots \times a_{k-1} \times \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} } \\ & \Leftrightarrow \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} \geq \sqrt[k]{ a_1 \times a_2 \times \cdots \times a_{k-1} \times \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} } \\ & \Leftrightarrow \left( \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} \right)^k \geq a_1 \times a_2 \times \cdots \times a_{k-1} \times \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} \\ & \Leftrightarrow \left( \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} \right)^{k-1} \geq a_1 \times a_2 \times \cdots \times a_{k-1}\\ & \Leftrightarrow \frac {a_1 + a_2 + \ldots a_{k-1} } {k-1} \geq \sqrt[k-1] { a_1 \times a_2 \times \cdots \times a_{k-1} } \end{aligned}\]

The last equation is the Arithmetic Mean-Geometric Mean Inequality for \( k-1\) variables. This completes the proof of the backward step. \( _\square \)

Note by Calvin Lin
4 years, 7 months ago

No vote yet
1 vote

  Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 \( 2 \times 3 \)
2^{34} \( 2^{34} \)
a_{i-1} \( a_{i-1} \)
\frac{2}{3} \( \frac{2}{3} \)
\sqrt{2} \( \sqrt{2} \)
\sum_{i=1}^3 \( \sum_{i=1}^3 \)
\sin \theta \( \sin \theta \)
\boxed{123} \( \boxed{123} \)

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...