Mathematical Induction
What you must understand
Induction proves statements about all positive integers. The structure is fixed: state the proposition (P(n)), prove the base case, assume (P(k)) true for some (k), then prove (P(k+1)) using that assumption, and conclude. Variants include strong induction (assume all cases up to (k)), induction starting from a base other than 1, and applications to divisibility, inequalities, sums, recurrences and matrix powers.
Traps
- Missing base case: the induction step alone proves nothing without a starting point.
- Not using the assumption: the step must genuinely invoke (P(k)); a proof that ignores it is not induction.
- Algebraic gaps: in divisibility proofs, factor out the divisor explicitly, e.g. show the expression equals (m) times the divisor.
- Inequality direction: when multiplying an inequality by a positive quantity, preserve direction; check positivity before multiplying.
- Conclusion wording: state clearly that (P(n)) holds for all (n) by induction.
- Strong induction necessity: for recurrences depending on two previous terms, ordinary induction may be insufficient.
Rule of thumb
In the inductive step, write down what you must prove, then deliberately engineer the appearance of the assumption (P(k)) in the expression for (P(k+1)).
Worked example
Prove (3^{n} - 1) is divisible by 2 for (n\ge 1).
Base: (n=1), (3-1=2), divisible by 2.
Assume (3^k - 1 = 2m). Then [ 3^{k+1} - 1 = 3\cdot 3^{k} - 1 = 3(2m+1) - 1 = 6m + 2 = 2(3m+1), ] which is divisible by 2. Hence true for all (n\ge 1).