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.
(36 intermediate revisions by 6 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 ''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 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 for ordinal numbers; see [[transfinite induction]].
