Discrete Math Home

## Strong Induction

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