Cauchy Induction
Cauchy Induction is a beautiful method of "Proof by Induction" discovered by Augustin Louis Cauchy.
Definition
For a given statement over the positive integers greater than or equal to 2, the technique of Cauchy Induction is to prove that is true, and that implies . This implies that is true for all positive . Then prove that implies . Then is true for all .
Along with , implying serves to show that is true for an arbitrarily large (in fact, here can be replaced with for any such that ). implying serves to show that if is true for some , it is true for all positive integers less than . Because every number is less than some arbitrarily large number, these statements together imply that is true for all integers .
Example
The AM-GM Inequality for variables, which states that for positive reals , can be proven using Cauchy Induction on :
The statement is true when because
Next we show that if AM-GM holds for variables, it also holds for variables:
The first inequality follows from -variable AM-GM, which is true by assumption, and the second inequality follows from 2-variable AM-GM, which is proven above.
Finally we show that if AM-GM holds for variables, it also holds for variables. By -variable AM-GM, Let Then we have So,
By Cauchy Induction, this proves the AM-GM inequality for variables.