Three forms of mathematical induction: Difference between revisions

Revision as of 19:09, 29 May 2005

Revision as of 23:29, 10 September 2005

Line 3:

# 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 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 when they are transfinite ordinal numbers; see [[transfinite induction]].

[Examples of each should be added.]