Waste less time on Facebook — follow Brilliant.
×

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
2 years, 8 months ago

No vote yet
1 vote

Comments

There are no comments in this discussion.

×

Problem Loading...

Note Loading...

Set Loading...