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 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); 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 k and n are natural numbers, but also for ordinal numbers; see transfinite induction.
[Examples of each should be added.]