Difference between revisions of "Cauchy Induction"
m |
(not a stub) |
||
(5 intermediate revisions by 4 users not shown) | |||
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> | + | 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>. |
− | {{ | + | |
+ | ==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. |
Latest revision as of 10:50, 25 July 2024
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
,
can be proven using Cauchy Induction on
:
The statement is true when because
Next we show that if AM-GM holds for variables, it also holds for
variables:
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,
Let
Then we have
So,
By Cauchy Induction, this proves the AM-GM inequality for variables.