Cauchy Induction

Cauchy Induction is a beautiful method of "Proof by Induction" discovered by Augustin Louis Cauchy.

Definition

For a given statement $s$ over the positive integers greater than or equal to 2, the technique of Cauchy Induction is to prove that $s(2)$ is true, and that $s(n)$ implies $s(2n)$ . This implies that $s(2^m)$ is true for all positive $m$ . Then prove that $s(n)$ implies $s(n-1)$ . Then $s(n)$ is true for all $n\geq 2$ .

Along with $s(2)$ , $s(n)$ implying $s(2n)$ serves to show that $s$ is true for an arbitrarily large $n$ (in fact, $s(2n)$ here can be replaced with $s(f(n))$ for any $f(n)$ such that $f(n)>n$ ). $s(n)$ implying $s(n-1)$ serves to show that if $s$ is true for some $n$ , it is true for all positive integers less than $n$ . Because every number is less than some arbitrarily large number, these statements together imply that $s$ is true for all integers $n\ge2$ .

Example

The AM-GM Inequality for $n$ variables, which states that for positive reals $a_1, a_2,\dots a_n$ , $\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}$ can be proven using Cauchy Induction on $n$ :

The statement is true when $n=2$ because $\frac{a_1+a_2}{2}\ge\sqrt{a_1a_2}\Leftrightarrow\left(a_1+a_2\right)^2\ge 4a_1a_2\Leftrightarrow\left(a_1-a_2\right)^2\ge0$

Next, we show that if AM-GM holds for $n$ variables, it also holds for $2n$ variables:

$\frac{a_1+a_2+\cdots+a_{2n}}{2n}=\frac{\frac{a_1+a_2+\cdots+a_n}{n}+\frac{a_{n+1}+a_{n+2}+\cdots+a_{2n}}{n}}{2}$ $\frac{\frac{a_1+a_2+\cdots+a_n}{n}+\frac{a_{n+1}+a_{n+2}+\cdots+a_{2n}}{n}}{2}\ge\frac{\sqrt[n]{a_1a_2\cdots a_n}+\sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}}{2}$ $\frac{\sqrt[n]{a_1a_2\cdots a_n}+\sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}}{2}\ge\sqrt{\sqrt[n]{a_1a_2\cdots a_n}\sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}}$ $\sqrt{\sqrt[n]{a_1a_2\cdots a_n}\sqrt[n]{a_{n+1}a_{n+2}\cdots a_{2n}}}=\sqrt[2n]{a_1a_2\cdots a_{2n}}$

The first inequality follows from $n$ -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 $n$ variables, it also holds for $n-1$ variables. By $n$ -variable AM-GM, $\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}$ . Let $a_n=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}$ . Then we have $\frac{a_1+a_2+\cdots+a_{n-1}+\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}}{n}=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}$ So $\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\ge\sqrt[n]{a_1a_2\cdots a_{n-1}\cdot \frac{a_1+a_2+\cdots+a_{n-1}}{n-1}}$ $\Rightarrow\left(\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\right)^n\ge a_1a_2\cdots a_{n-1}\cdot \frac{a_1+a_2+\cdots+a_{n-1}}{n-1}$ $\Rightarrow\left(\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\right)^{n-1}\ge a_1a_2\cdots a_{n-1}$ $\Rightarrow \frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\ge\sqrt[n-1]{a_1a_2\cdots a_{n-1}}$

By Cauchy Induction, this proves the AM-GM inequality for $n$ variables.

Page

Toolbox

Search

Cauchy Induction

Definition

Example