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"
m (→‎Definition)
Line 2: Line 2:
  
 
==Definition==
 
==Definition==
−
For a given statement <math>s</math> over the positive integers greater than or equal to 2, the technique of Cauchy Induction is to prove that <math>s(2)</math> is true, and that <math>s(n)</math> implies <math>s(2n)</math>. This implies that <math>S(2^m)</math> is true for all positive <math>m</math>. Then prove that <math>s(n)</math> implies <math>s(n-1)</math>. Then <math>s(n)</math> is true for all <math>n\geq 2</math>.
+
For a given statement <math>s</math> over the positive integers greater than or equal to 2, the technique of Cauchy Induction is to prove that <math>s(2)</math> is true, and that <math>s(n)</math> implies <math>s(2n)</math>. This implies that <math>s(2^m)</math> is true for all positive <math>m</math>. Then prove that <math>s(n)</math> implies <math>s(n-1)</math>. Then <math>s(n)</math> is true for all <math>n\geq 2</math>.
−
 
 
−
Along with <math>s(2)</math>, <math>s(n)</math> implying <math>s(2n)</math> serves to show that <math>s</math> is true for an arbitrarily large <math>n</math> (in fact, <math>s(2n)</math> here can be replaced with <math>s(f(n))</math> for any <math>f(n)</math> such that <math>f(n)>n</math>). <math>s(n)</math> implying <math>s(n-1)</math> serves to show that if <math>s</math> is true for some <math>n</math>, it is true for all positive integers less than <math>n</math>. Because every number is less than some arbitrarily large number, these statements together imply that <math>s</math> is true for all integers <math>n\ge2</math>.  
 
  
 +
Along with <math>s(2)</math>, <math>s(n)</math> implying <math>s(2n)</math> serves to show that <math>s</math> is true for an arbitrarily large <math>n</math> (in fact, <math>s(2n)</math> here can be replaced with <math>s(f(n))</math> for any <math>f(n)</math> such that <math>f(n)>n</math>). <math>s(n)</math> implying <math>s(n-1)</math> serves to show that if <math>s</math> is true for some <math>n</math>, it is true for all positive integers less than <math>n</math>. Because every number is less than some arbitrarily large number, these statements together imply that <math>s</math> is true for all integers <math>n\ge2</math>.
  
 
==Example==
 
==Example==

Revision as of 00:35, 27 September 2015

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.

This article is a stub. Help us out by expanding it.

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