Three forms of mathematical induction: Difference between revisions

Revision as of 23:01, 3 November 2004

Revision as of 23:03, 3 November 2004

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 proveda howevervacuously possibletrue (itspecial iscase assumedof truewhat 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.]