Difference between revisions of "Cauchy Induction"
m |
|||
| Line 4: | Line 4: | ||
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>. | ||
| − | [[Category: | + | 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== | ||
| + | |||
| + | The AM-GM Inequality for <math>n</math> variables, which states that for positive reals <math>a_1, a_2,\dots a_n</math>, | ||
| + | <cmath>\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}</cmath> | ||
| + | can be proven using Cauchy Induction on <math>n</math>: | ||
| + | |||
| + | The statement is true when <math>n=2</math> because | ||
| + | <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: | ||
| + | |||
| + | <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{\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}</cmath> | ||
| + | <cmath>\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}}}</cmath> | ||
| + | <cmath>\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}}</cmath> | ||
| + | |||
| + | 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. | ||
| + | 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 | ||
| + | <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, | ||
| + | <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-1}\ge a_1a_2\cdots a_{n-1}</cmath> | ||
| + | <cmath>\Rightarrow \frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\ge\sqrt[n-1]{a_1a_2\cdots a_{n-1}}</cmath> | ||
| + | |||
| + | By Cauchy Induction, this proves the AM-GM inequality for <math>n</math> variables. | ||
| + | |||
| + | [[Category:Example]] | ||
{{stub}} | {{stub}} | ||
Revision as of 10:06, 9 June 2012
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 
,
![\[\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}\]](http://latex.artofproblemsolving.com/b/5/d/b5d2d4150ba03f50b68867ccfbb6f46828dc0cdb.png)
can be proven using Cauchy Induction on :
The statement is true when 
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\]](http://latex.artofproblemsolving.com/e/5/8/e580029ac4744f5146c51ea9e53c1557baa4375e.png)
Next we show that if AM-GM holds for variables, it also holds for 
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}\]](http://latex.artofproblemsolving.com/1/b/3/1b38e242423491c4a3e0fbba4232cc9727a2964e.png)
![\[\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}\]](http://latex.artofproblemsolving.com/5/8/8/58819fdfe9a026789ce21420a96fe507c61c0f97.png)
![\[\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}}}\]](http://latex.artofproblemsolving.com/b/a/3/ba3edbee86ea4c62114f6e1be92c7ed7b4093687.png)
![\[\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}}\]](http://latex.artofproblemsolving.com/b/c/8/bc839d16deb2569a8a18e9c960afee4c7400d76d.png)
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, ![$\frac{a_1+a_2+\cdots+a_n}{n}\ge\sqrt[n]{a_1a_2\cdots a_n}$](http://latex.artofproblemsolving.com/c/6/c/c6cc278a33e14bf3b64ef634109c2ef6f30f4e41.png)
Let 
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}\]](http://latex.artofproblemsolving.com/4/c/c/4cc87dd4038ae072d43120c56d67d9c6128ac970.png)
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}}\]](http://latex.artofproblemsolving.com/5/3/8/538431280fa01a61938f7acd1e8146a6d126fa10.png)
![\[\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}\]](http://latex.artofproblemsolving.com/2/8/f/28f0128377aee4596a1491b386f2efd5b79c4a57.png)
![\[\Rightarrow\left(\frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\right)^{n-1}\ge a_1a_2\cdots a_{n-1}\]](http://latex.artofproblemsolving.com/d/8/b/d8b9f3010aa6ff8199f6355ee46e6f3cf7dfd149.png)
![\[\Rightarrow \frac{a_1+a_2+\cdots+a_{n-1}}{n-1}\ge\sqrt[n-1]{a_1a_2\cdots a_{n-1}}\]](http://latex.artofproblemsolving.com/0/a/c/0ac60d4ba34e8d4ca6efb6601b790fe3528d5200.png)
By Cauchy Induction, this proves the AM-GM inequality for variables.
This article is a stub. Help us out by expanding it.
