The main ideas here have been incorporated into mathematical induction, and both articles are still in a less-than-statisfactory state. I'm redirecting this to that article.
(46 intermediate revisions by 11 users not shown)
Line 1:
#REDIRECT[[mathematical induction]]
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 <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 whoever 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]].
