mathematical induction

Mathematical induction is the standard technique for proving that a statement P(n) holds for every natural number n. The image is a row of dominoes: if you knock over the first one (the base case), and you have arranged that each domino knocks over the next (the inductive step), then all of them fall. You verify just two things, yet conclude infinitely many.

Precisely, to prove “P(n) for all n ≥ n0” you establish (1) the base case P(n0), and (2) the inductive step: for every k ≥ n0, the implication P(k) ⇒ P(k+1). The temporary assumption P(k) used in step (2) is the induction hypothesis; you assume the statement at one stage in order to deduce it at the next. From these two facts the principle delivers P(n) for every n ≥ n0.

A common variant is strong (or complete) induction, where the step may assume P(j) for all j from n0 up to k, not merely P(k); this is logically equivalent to ordinary induction but is convenient when P(k+1) depends on several earlier cases. Induction is not guessing-from-examples (that is empirical and unreliable); it is a rigorous deductive principle, equivalent to the well-ordering of the naturals. A frequent error is omitting or mis-stating the base case — without a first domino, nothing falls, however good the step.