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.
(44 intermediate revisions by 10 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 ''P''(''k'') is true for all ''k'' < ''n'' then ''P''(''n'') is true (proof by ''complete induction''); the first, or basic, case is proved however possible (it is assumed true in the induction step). This form works not only when the values of ''k'' and ''n'' are natural numbers, but also when they are transfinite ordinal numbers; see [[transfinite induction]].
