Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Cauchy Induction"
(not a stub)
 
(One intermediate revision by one other user not shown)
(No difference)

Latest revision as of 09:50, 25 July 2024

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.

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Cauchy_Induction&oldid=223615"