Three forms of mathematical induction: Difference between revisions

Revision as of 20:22, 3 November 2004

Revision as of 20:22, 3 November 2004

Line 3:

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

#The basis for induction is [[vacuous truth|vacuously true]]; the step that goes from case <i>n</i> to case <i>n</i> + 1 is trivial if <i>n</i> > 1 and impossible if <i>n</i> = 1; the substantial part of the proof is the case <i>n</i> = 2. The case <i>n</i> = 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''); the first, or basic, case is proved whoeverhowever possible (it is assumed true 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.]