Combinatorics • Topic 17

Strong Induction

Strong Induction is a variation where we assume the statement holds for all smaller values, not just the immediate predecessor.

Structure of Proof

To prove $P (n)$ for all $n \geq k$ :

Base Case(s): Verify $P (k)$ (and sometimes $P (k + 1), \dots$ depending on the recurrence).
Strong Hypothesis: Assume $P (j)$ is true for all $k \leq j \leq m$ .
Inductive Step: Prove $P (m + 1)$ using the fact that all previous cases are true.

When to Use It?

Use Strong Induction when

P (m + 1)

depends on values smaller than

m

(like

m - 1

m /2

Prime factorization proofs (depends on factors of $n$ , not $n - 1$ ).
Recurrences like $F_{n} = F_{n - 1} + F_{n - 2}$ .
Game theory (winning positions depend on all possible moves to smaller states).

Example (Fundamental Theorem of Arithmetic)

Prove every integer

n \geq 2

can be written as a product of primes.

Proof. Base Case ( $n = 2$ ): 2 is prime. True. Hypothesis: Assume every integer $j$ with $2 \leq j \leq m$ has a prime factorization. Step ( $n = m + 1$ ):

Case 1: $m + 1$ is prime. Done.
Case 2: $m + 1$ is composite. Then $m + 1 = ab$ where $1 < a, b < m + 1$ .

By the strong hypothesis, both

a

and

b

have prime factorizations. Multiplying them gives the factorization for

m + 1

. ∎

Practice Problems

Exercise (Problem 1)

The sequence

a_{n}

is defined by

a_{1} = 1, a_{2} = 2, a_{3} = 3

and

a_{n} = a_{n - 1} + a_{n - 2} + a_{n - 3}

. Prove that

a_{n} < 2^{n}

Exercise (Problem 2)

Prove that every amount of postage of 12 cents or more can be formed using only 4-cent and 5-cent stamps. (Hint: Base cases 12, 13, 14, 15. Then $P (n) ⟹ P (n + 4)$ ).

Exercise (Problem 3)

A "triangulation" divides a polygon into triangles using non-intersecting diagonals. Prove that every triangulation of an

n

-gon (

n \geq 3

) uses exactly

n - 2

triangles.