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.
Theorem: For all nonnegative integers n, 1 + 2 + ... + n = n(n + 1)/2. Proof: For n = 0, the statement is trivial: the sum has no terms and is 0, and the quantity on the right is also 0. Suppose the statement is true for n. Add n + 1 to both sides and you get: 1 + 2 + ... + n + (n + 1) = (n)(n + 1)/2 + (2)(n + 1)/2 = (n + 1)(n + 2)/2. This is just the n + 1 version of the statement, and induction finishes the proof.
- 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 when they are transfinite ordinal numbers; see transfinite induction.
[Examples of each should be added.]