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> | + | 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== | ==Example== |
Revision as of 01:35, 27 September 2015
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.
This article is a stub. Help us out by expanding it.