Each proof by mathematical induction has one of three forms.
- The basis for induction is trivial; the substantial part of the proof goes from case n to case n + 1.
- The basis for induction is vacuously true; the step that goes from case n to case n + 1 is trivial if n ≥ 2 and impossible if n = 1; the substantial part of the proof is the case n = 2. 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. It is vacuously true because no value of k is smaller than the smallest possible one. 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.
