Theorem 5.2: (Strong Induction) Let P(n ) be a statement which depends on a natural number n. If P(n_o) is true for some natural number no and if P(k ) is true for all n_o < k < m implies that P(m ) is true, then P(n ) is true for all natural numbers n > n_o.

Proof: Assume that P(n_o) is true and if P(k) is true for all n_o < k < m mplies that P(m) is true. Suppose that there is some natural number n > no for which P(n) is not true. Then

By Theorem 5.1, the well ordering principle, there is a least element n₁ in this set. Since n₁ is the smallest element in the set, P (k ) is true for all no < k < n₁. But by the strong induction hypotheses this implies that P(n₁) is true which is a contradiction.