The strong induction or complete induction is used to prove a statement that cannot be easily proved by mathematical induction.

Strong induction:
For a given integer \(a\), the statement \(P(n)\) is true for all positive integers \(n\geq a\) if we complete the following two steps.
Basis step: Show \(P(a)\) is true.
Inductive step: Assume that \(P(a)\), \(P(a+1)\), ..., \(P(k)\) are true for some integer \(k\geq a\) (inductive hypothesis). Show \(P(k+1)\) is true.

Example. Prove that any integer \(n > 1\) can be written as a product of primes.

Proof. For all integers \(n > 1\), let \(P(n)\) be the statement \[``n \text{ is a product of primes.}"\] Basis step: \(2\) is a product of one prime \(2\). Thus \(P(2)\) is true.
Inductive step: Assume that \(P(2)\), \(P(3)\), ..., \(P(k)\) are true for some positive integer \(k\geq 2\), i.e., \[n \text{ is a product of primes for } n=2,3,\ldots,k \text{ (inductive hypothesis)}.\] We show \(P(k+1)\) is true, i.e., \[k+1 \text{ is a product of primes.}\] If \(k+1\) is prime, then \(k+1\) is a product of primes. Suppose \(k+1\) is composite. Then \(k+1=ab\) for some integers \(a\) and \(b\) where \(2\leq a,b\leq k\). Since \(2\leq a,b\leq k\), \(P(a)\) and \(P(b)\) are true by the inductive hypothesis. Then \(a\) and \(b\) are product of primes and consequently so is \(k+1=ab\). Thus \(P(k+1)\) is true.
By strong induction, \(P(n)\) is true for all positive integers \(n\geq 2\).

Remark. Although strong induction seems "stronger" than mathematical induction, it can be shown that they are equivalent.

Last edited