Three forms of mathematical induction: Difference between revisions

Revision as of 02:41, 6 March 2006

Revision as of 22:44, 6 March 2006

Line 11:

[[Category:Pages for deletion]]

<!-- End of AfD message, feel free to edit beyond this point -->

This article presumes familiarity with [[mathematical induction]]. That article, not this one, is the appropriate source of information for those not so familiar.

==The three forms==

Proofs that a subset of { 1, 2, 3, ... } is in fact the whole set { 1, 2, 3, ... } by [[mathematical induction]] usually have one of the following three forms. They are collected here in order to show the contrast between them, and its coexistence with the commonality between them.

===First form===

# The basis for induction is trivial; the substantial part of the proof goes from case ''n'' to case ''n'' + 1.

#The case ''n'' = 1 is [[vacuous truth|vacuously true]]; the step that goes from case ''n'' to case ''n'' + 1 is trivial if ''n'' > 1 and impossible if ''n'' = 1; the substantial part of the proof is the case ''n'' = 2, and the case ''n'' = 2 is relied on in the trivial induction step.

* The basis for induction is trivial;

# The induction step shows that if <i>P</i>(<i>k</i>) is true for all <i>k</i> < <i>n</i> then <i>P</i>(<i>n</i>) is true (proof by [[complete induction]]); no basis for induction is needed because the first, or basic, case is a vacuously true special case of what is proved in the induction step. This form works not only when the values of <i>k</i> and <i>n</i> are natural numbers, but also for ordinal numbers; see [[transfinite induction]].

# The basis for induction is trivial;* the substantial part of the proof goes from case ''n'' to case ''n'' + 1.

===Second form===

* The case ''n'' = 1 is [[vacuous truth|vacuously true]];

* the step that goes from case ''n'' to case ''n'' + 1 is trivial if ''n''&nbsp;&ge;&nbsp;2 and impossible if ''n'' = 1;

#The case ''n'' = 1 is [[vacuous truth|vacuously true]]; the step that goes from case ''n'' to case ''n'' + 1 is trivial if ''n'' > 1 and impossible if ''n'' = 1;* the substantial part of the proof is the case ''n'' = 2, and the case ''n'' = 2 is relied on in the trivial induction step.

===Third form===

* The induction step shows that if ''P''(''k'') is true for all ''k'' < ''n'' then ''P''(''n'') is true (proof by [[complete induction]]);

* no basis for induction is needed because the first, or basic, case is a vacuously true special case of what is proved in the induction step.

This form works not only when the values of ''k'' and ''n'' are natural numbers, but also for ordinal numbers; see [[transfinite induction]].

==Examples==

This is not the appropriate place to go into details of proofs, but rather only broad outlines of proofs are shown. For examples of proofs by mathematical induction with full details, see [[mathematical induction]].

===First form===

Most proofs by mathematical induction that are adduced as examples when mathematical induction is first taught are of the first form.

===Second form===

* The usual product rule taught in [[calculus]] says

::<math>(fg)' = f'g + g'f.\,</math>

:For a product of ''n'' functions, one has

::<math>(f_1 f_2 f_3 \cdots f_n)' \,</math>

:::<math>= (f_1' f_2 f_3 \cdots f_n)

+ (f_1 f_2' f_3 \cdots f_n)

+ (f_1 f_2 f_3'\cdots f_n)+\cdots +(f_1 f_2 \cdots f_{n-1} f_n').\, </math>

:In each of the ''n'' terms, just one of the factors is a derivative; the others are not.

:Now observe four facts:

**If ''n'' = 1, then the proposition just says

:::<math>f' = f'.\,</math>

::It can be said that just one factor is a derivative, and it is [[vacuous truth|vacuously true]] that the others are not, because there are not others!

**To go from case ''n'' to case ''n'' + 1 is trivial if ''n''&nbsp;&ge;&nbsp;2.

**To go from case ''n'' to case ''n'' + 1, one must ''use'' the case ''n''&nbsp;=&nbsp;2.

**The substantial part of the proof is the case ''n'' = 2, and that is precisely the product rule that is taught differential calculus.

[More examples to be added.]

[Examples of each should be added.]

[[Category:Mathematical logic]][[Category:Proofs]]