What Makes Strong Induction Strong?

In introductory discrete mathematics, we are introduced to a powerful proof technique called the principle of mathematical induction, which is commonly formulated as follows.

Mathematical Induction. Let $\phi$ be a predicate on $\mathbb N$ . Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(k) \Rightarrow \phi(k+1)$ . Then for any $n \in \mathbb N$ , $\phi(n)$ .

Proof of Mathematical Induction. Let $K := \{n \in \mathbb N : \phi(n)\} \subseteq \mathbb N$ . By the first condition, $0 \in K$ . By the second condition, we obtain the equivalent formulation $k \in K \Rightarrow k+1 \in K$ . By a core property of $\mathbb N$ , $K = \mathbb N$ .

The condition $\phi(0)$ is known as the base case and the condition “for any $k \in \mathbb N$ , $\phi(k) \Rightarrow \phi(k+1)$ ” is known as the induction step. Students are introduced to a stronger variant of induction known as strong induction.

Strong Induction. Let $\phi$ be a predicate on $\mathbb N$ . Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k) \Rightarrow \phi(k+1)$ . Then for any $n \in \mathbb N$ , $\phi(n)$ .

The difference here is that we have more tools to work with. We will use strong induction to prove the existence part of the fundamental theorem of arithmetic.

Proof of Strong Induction. Suppose $\phi(0)$ and for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k) \Rightarrow \phi(k+1)$ . Let $\Phi$ be the predicate defined on $\mathbb N$ by

$\Phi(n) = (\forall k\in \mathbb N\quad (k \leq n \ \Rightarrow \ \phi(k))).$

We will use standard induction to prove that for any $n\in \mathbb N$ , $\Phi(n)$ . Since $n \leq n$ , this implies $\phi(n)$ , as required.

For the base case, fix $k \in \mathbb N$ such that $k \leq 0$ . Then $k = 0$ , and by the first condition, $\phi(k) = \phi(0)$ holds. Therefore, $\Phi(0)$ .

For the induction step, fix $k \in \mathbb N$ and suppose $\Phi(k)$ . By definition, for any $m \in \mathbb N$ , $m \leq k$ implies $\phi(m)$ . Therefore, $\phi(0),\phi(1),\dots,\phi(k)$ . By the second condition, $\phi(k+1)$ . Therefore, for any $m \in \mathbb N$ , $m \leq k+1$ implies $\phi(m)$ . This is equivalent to $\Phi(k+1)$ . Therefore, $\Phi(k+1)$ , as required.

Therefore, $\Phi(0)$ and for any $k \in \mathbb N$ , $\Phi(k)$ implies $\Phi(k+1)$ . By induction, for any $n \in \mathbb N$ , $\Phi(n)$ , as required.

As promised, we prove that every natural number can be factored into a unique product of primes.

Fundamental Theorem of Arithmetic. For any number $n \in \mathbb N$ such that $n \geq 2$ , there exist primes $p_1,\dots,p_N$ such that

$\displaystyle n = p_1 \cdots p_N = \prod_{k=1}^N p_k.$

Furthermore, the factorisation is unique in the following sense: if $p_1 \leq \dots \leq p_N$ and $q_1 \leq \dots \leq q_M$ are primes such that

$\displaystyle n = \prod_{i=1}^N p_i = \prod_{j=1}^M q_j,$

then $M=N$ and for any $1 \leq i \leq N$ , $p_i = q_i$ .

Proof of the Fundamental Theorem of Arithmetic. We will use strong induction to establish existence. Let $\phi$ be a predicate on $\mathbb N$ defined by $\phi(n)$ precisely when $n + 2$ can be factored into primes. Clearly, $0 +2 = 2$ is factored into the prime $2$ , so that $\phi(0)$ . Suppose for any $k \in \mathbb N$ , $\phi(0),\phi(1),\dots,\phi(k)$ . We need to establish $\phi(k+1)$ .

Consider the number $k+1 +2 = k +3$ . There are two cases. Either $k+3$ is prime, or not. If $k+3$ is prime, then it is factored into $k+3$ , as required. If $k+3$ is not prime, then $k+3$ is composite. This means that there exist positive integers $r, s \geq 2$ such that $k+3 = rs >\max\{r, s\}$ . Since $2 \leq r, s < k+1+2$ , by the induction hypothesis, there exist primes $p_i$ and $q_j$ such that

$\displaystyle r = \prod_{i = 1}^N p_i,\quad s = \prod_{j = 1}^M q_j.$

Hence, letting $r_l$ denote the primes in non-decreasing sequence,

$\displaystyle k+3 = rs = \prod_{i = 1}^N p_i \cdot \prod_{j = 1}^M q_j = \prod_{l = 1}^{M+N} r_l,$

as required. Therefore, for any $n \in \mathbb N$ , $\phi(n)$ . This is equivalent to the original existence proposition.

We will use Euclid’s lemma to establish uniqueness, for the sake of completeness. As an aside, Euclid’s lemma will be proved independently from the fundamental theorem of arithmetic, so that we do not incur a circular-reasoning fallacy.

Suppose $p_1 \leq \dots \leq p_N$ and $q_1 \leq \dots \leq q_M$ are primes such that

$\displaystyle n = \prod_{i=1}^N p_i = \prod_{j=1}^M q_j.$

We claim that $p_1 = q_1$ . Repeating the argument $\min\{N,M\}$ times then yields the result. Fix $i$ . By Euclid’s lemma, there exists $j$ such that $p_i \mid q_j$ . Thus, there exists some integer $k$ such that $q_j = kp_i$ . Since $q_j$ is prime, $q_j \mid k$ or $q_j \mid p_i$ .

If $q_j \mid k$ , find an integer $l$ such that $k = q_j l$ . Then $q_j = kp_i = q_j l p_i \Rightarrow lp_i = 1 \Rightarrow p_i = 1$ , a contradiction.
If $q_j \mid p_i$ , then a similar argument yields $p_i = q_j$ .

Next, we show that $p_1 = q_1$ . Otherwise, there exists $j$ such that $q_1 < q_j = p_1$ . By Euclid’s lemma again, there exists $i$ such that $q_1 \mid p_i$ . A similar argument yields $q_1 = p_i \geq p_1 > q_1$ , a contradiction.

To conclude, strong induction affords us not just $\phi(k)$ , from which we need to prove $\phi(k+1)$ , but furthermore the whole sleuth of $\phi(0),\phi(1),\dots,\phi(k)$ , using any of which or even any combination thereof, to prove $\phi(k+1)$ .

—Joel Kindiak, 13 Nov 24, 0017H

Responses

A Classic Numbers Challenge – KindiakMath

December 12, 2024 at 3:02 pm

[…] We have shown that every number can be broken down into a unique product of primes, known as the fundamental theorem of arithmetic. […]

LikeLike

Atomic Numbers – KindiakMath

December 26, 2024 at 6:04 pm

[…] Proof. We prove this result independently here. […]

LikeLike

The Power of Permutations – KindiakMath

June 9, 2025 at 1:13 am

[…] Fix a permutation . Define the predicate on by . We will perform strong induction on the number of elements that satisfy . If there are exactly such elements, then we have the […]

LikeLike

Generalised Diagonalisation – KindiakMath

July 21, 2025 at 7:20 pm

[…] I think this proof sketch more-or-less provides the key steps and intuition required to prove Theorem 1. Check out a more complete proof in this link, which effectively formalises our ideas using mathematical induction. […]

LikeLike

Prime Factorisation – KindiakMath

September 18, 2025 at 2:46 am

[…] the fundamental theorem of arithmetic, write natural numbers in the […]

LikeLike

Polynomial Long Division – KindiakMath

October 15, 2025 at 4:07 pm

[…] We will prove the case by strong induction on . If , then implies the constant function , so […]

LikeLike

Who Cares About Well-Ordering? – KindiakMath

December 28, 2025 at 12:47 am

[…] The well-ordering principle helps us prove the existence of . But how do we even know that the well-ordering principle is a logically valid theorem? It turns out to be a consequence of strong induction. […]

LikeLike

The Preconditions of Infinity – KindiakMath

December 28, 2025 at 1:04 am

[…] can make this calculation airtight using a quick exercise in mathematical induction. In particular, […]

LikeLike

The Size of Finity – KindiakMath

December 28, 2025 at 1:05 am

[…] Proof. We will prove this result by induction. […]

LikeLike

What Makes Strong Induction Strong?

Share this:

Responses

Leave a comment Cancel reply