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 (specifically for all powers of ). In the backward argument, we will show that if the statement is true for variables, then it is also true for variables. By combining these arguments, we show that the statement is true for any value of , by first applying the forward argument to show that it is true for a power of 2 that is larger than , and then using the backward argument to show that it is true for .
Arithmetic Mean - Geometric Mean Inequality
AM-GM inequality: For non-negative real values ,
Proof: (Forward) We will show this by induction. The base case is proved in Complete the Square. For the induction step, suppose the statement is true for some ; we would like to show that the statement is true for . Given positive real values, we divide the set in half (obtaining and ), and then apply the induction hypothesis to each set.
The first inequality follows from using the Induction Hypothesis twice, while the second inequality follows from the 2-variable case, by setting and . This completes the argument for the forward step.
(Backward) We will now show that if the statement is true for , then it is also true for . Assume that the statement is true for any set of positive real values, i.e. that
Then, it will be true for the k variables
The last equation is the Arithmetic Mean-Geometric Mean Inequality for variables. This completes the proof of the backward step.