Three forms of mathematical induction: Difference between revisions

Revision as of 18:56, 29 May 2005

Revision as of 19:02, 29 May 2005

Line 1:

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.

# The basis for induction is trivial; the substantial part of the proof goes from case ''n'' to case ''n'' + 1. Example of this technique:<br>

Theorem: For all nonnegative integers ''n'',<br>

1 + 2 + ... + ''n'' = ''n''(''n'' + 1)/2.<br>

Proof: For ''n'' = 0, the statement is trivial: the sum has no terms and is 0, and the quantity on the right is also 0. Suppose the statement is true for ''n''. Add ''n'' + 1 to both sides and you get:<br>

1 + 2 + ... + ''n'' + (''n'' + 1) = (''n'')(''n'' + 1)/2 + (2)(''n'' + 1)/2 = (''n'' + 1)(''n'' + 2)/2.<br>

This is just the ''n'' + 1 version of the statement, and induction finishes the proof.

# 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]].