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)
m (→‎Example)
 
Line 15: Line 15:
 
<cmath>\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</cmath>
 
<cmath>\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</cmath>
  
−
Next we show that if AM-GM holds for <math>n</math> variables, it also holds for <math>2n</math> variables:
+
Next, we show that if AM-GM holds for <math>n</math> variables, it also holds for <math>2n</math> variables:
  
 
<cmath>\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}</cmath>
 
<cmath>\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}</cmath>
Line 24: Line 24:
 
The first inequality follows from <math>n</math>-variable AM-GM, which is true by assumption, and the second inequality follows from 2-variable AM-GM, which is proven above.  
 
The first inequality follows from <math>n</math>-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 <math>n</math> variables, it also holds for <math>n-1</math> variables.  
+
Finally, we show that if AM-GM holds for <math>n</math> variables, it also holds for <math>n-1</math> variables.  
−
By <math>n</math>-variable AM-GM, <math>\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}</math>
+
By <math>n</math>-variable AM-GM, <math>\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}</math>.
−
Let <math>a_n=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}</math> Then we have
+
Let <math>a_n=\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}</math>. Then we have
 
<cmath>\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}</cmath>
 
<cmath>\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}</cmath>
−
So,
+
So
 
<cmath>\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}}</cmath>
 
<cmath>\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}}</cmath>
 
<cmath>\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}</cmath>
 
<cmath>\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}</cmath>

Latest revision as of 19:41, 1 February 2025

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=241682"