Revision as of 22:16, 28 January 2004 edit Michael Hardy (talk \| contribs) Administrators 210,596 edits No edit summary ← Previous edit		Revision as of 22:19, 28 January 2004 edit undo Michael Hardy (talk \| contribs) Administrators 210,596 edits m Apparently you can't do this automatic numbering unless you leave no space between lines, and unless you use automatic rather than manual, the indentations don't look good. Next edit →
Line 1: Proofs by [[mathematical induction]] usually have one of the following three forms. 1.# The basis for induction is trivial; the substantial part of the proof goes from case <i>n</i> to case <i>n</i> + 1. 2. #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.▼ 3.# 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]].▼ ▲2. 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. ▲3. 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.]

Three forms of mathematical induction: Difference between revisions