Strong Induction | Real Analysis

Draw the factorization tree of

n = 30

and strong induction explains itself — the splits drop to much smaller numbers like

15

and

2

, not to

n - 1 = 29

. Slide

n

, watch the tree redraw, and follow the induction step that assumes all of

P(2), \dots, P(n-1)

at once; the weak hypothesis

P(n-1)

alone can never reach the factors.

Examples & Exercises

Prove by strong induction that every integer $n \ge 2$ is a product of primes. Split into the cases where $n$ is prime and where $n = a \cdot b$ is composite ( $1 < a, b < n$ ), and pinpoint exactly where the weak-induction step ("assume $P(n-1)$ , prove $P(n)$ ") breaks down: the factors $a, b$ of $n$ are typically nowhere near $n - 1$ , so $P(n-1)$ says nothing about them.

P(n):\ n\ \text{is a product of primes},\qquad n \ge 2

\text{assume } P(2), \dots, P(n-1);\quad \text{prove } P(n)

n = 30 = 2 \times 3 \times 5

: composite, first split

a = 2

b = 15

— nowhere near

n-1 = 29

Show proof

Set up the strong-induction hypothesis: for some $n \ge 2$ , assume $P(k)$ holds for every $2 \le k < n$ — i.e. each such $k$ is a product of primes. Prove $P(n)$ .
Case 1: $n$ is prime. Then $n$ is itself a "product of primes" (a product with one factor). This is the base-like case; there is nothing to prove.
Case 2: $n$ is composite. Then $n = a \cdot b$ for some $1 < a, b < n$ . Since $a < n$ , the strong hypothesis $P(a)$ applies and gives $a = p_1 \cdots p_r$ as a product of primes; likewise $b = q_1 \cdots q_s$ . Hence $n = p_1 \cdots p_r \cdot q_1 \cdots q_s$ — a product of primes. This proves $P(n)$ .
Where weak induction stalls: weak induction supplies only $P(n-1)$ . But for $n = 30$ what is needed is not $P(29)$ — it is $P(2)$ and $P(15)$ , because the factors $a = 2$ , $b = 15$ are nowhere near $n - 1 = 29$ . The hypothesis $P(n-1)$ says nothing about $a$ and $b$ , so the weak step cannot proceed. The proof works precisely because the strong hypothesis covers every number below $n$ .
$n = 30 = 2 \times 15:\quad P(2), P(15)\ \text{needed},\quad P(29)\ \text{useless}$

Prove by strong induction that every integer $n \ge 12$ can be written as $4a + 5b$ with integers $a, b \ge 0$ . Check the four base cases $12 = 3 \cdot 4$ , $13 = 2 \cdot 4 + 5$ , $14 = 4 + 2 \cdot 5$ , $15 = 3 \cdot 5$ ; for $n \ge 16$ apply the hypothesis to $n - 4$ and add one 4-stamp. Explain why exactly four consecutive base cases are needed (the induction step jumps back by 4).

P(n):\ \exists a, b \ge 0\ \text{with}\ n = 4a + 5b,\qquad n \ge 12

n \ge 16 \;\Rightarrow\; n - 4 \ge 12:\quad n = (n-4) + 4

n = 30 = 5 \cdot 4 + 2 \cdot 5 = 20 + 10

a = 5

b = 2

Show proof

Base cases: $12 = 3 \cdot 4 + 0 \cdot 5$ ( $a = 3$ , $b = 0$ ), $13 = 2 \cdot 4 + 1 \cdot 5$ ( $a = 2$ , $b = 1$ ), $14 = 1 \cdot 4 + 2 \cdot 5$ ( $a = 1$ , $b = 2$ ), $15 = 0 \cdot 4 + 3 \cdot 5$ ( $a = 0$ , $b = 3$ ) — each checked directly.
Induction step: let $n \ge 16$ and assume $P(k)$ for all $12 \le k < n$ (strong induction). Since $n - 4 \ge 12$ , the hypothesis applies to $n - 4$ , giving $n - 4 = 4a + 5b$ for some $a, b \ge 0$ . Adding 4 to both sides, $n = 4(a+1) + 5b$ — proving $P(n)$ .
Why four consecutive base cases: the induction step jumps back by 4, from $n$ to $n - 4$ . So for the proof of $n \ge 16$ to "land" on one of $12, 13, 14, 15$ , every remainder class $0, 1, 2, 3$ modulo 4 must be present among the bases. With only three, one residue class would be left hanging. In general a jump of $m$ needs $m$ consecutive base cases. Example: $30 - 4 \cdot 4 = 14$ , so $30 = (\text{expression for } 14) + 4 \cdot 4 = (4 + 2 \cdot 5) + 16 = 5 \cdot 4 + 2 \cdot 5$ .

Prove by strong induction that every integer $n \ge 2$ has a prime divisor. If $n$ is prime it divides itself; if $n = a \cdot b$ is composite ( $1 < a < n$ ), apply the hypothesis at $a$ — a prime divisor $p$ of $a$ also divides $n$ .

P(n):\ \exists\ \text{prime } p\ \text{with}\ p \mid n,\qquad n \ge 2

n = a \cdot b,\ 1 < a < n:\quad p \mid a \;\Rightarrow\; p \mid n

n = 36 = 2^2 \cdot 3^2

: prime divisors 2 and 3. In the tree,

36 = 2 \times 18

→

18 = 2 \times 9

→

9 = 3 \times 3

Show proof

Set up the strong-induction hypothesis: for some $n \ge 2$ , assume every $2 \le k < n$ has a prime divisor. Prove $P(n)$ .
Case 1: $n$ is prime. Then $n$ itself is a prime divisor of $n$ ( $n \mid n$ ).
Case 2: $n$ is composite. Then $n = a \cdot b$ for some $1 < a, b < n$ . Since $a < n$ , the hypothesis applies at $a$ , giving a prime $p$ with $p \mid a$ . Because $a \mid n$ (as $n = a \cdot b$ ), transitivity of divisibility yields $p \mid n$ . So $p$ is a prime divisor of $n$ .
$p \mid a,\ a \mid n \;\Rightarrow\; p \mid n \quad (\text{transitivity})$
Remark: this theorem is the "one-step" version of problem 1 (full factorization). For $n = 36$ the hypothesis is applied at $a = 2$ , yielding $p = 2$ , and $2 \mid 2$ with $2 \mid 36$ finishes it. The existence of a single prime divisor follows from the same strong-induction skeleton, without computing the whole factorization.