Grade 11

Mathematical Induction

Proving statements for all natural numbers via base case and inductive step, strong induction, well-ordering, and where induction fails.

Imagine an infinite line of dominoes standing upright. How can we be sure every single domino will fall? Two things are enough: (1) we push the first domino over, and (2) whenever any domino falls, it stands close enough to knock over the next one. Mathematical induction is this exact domino chain turned into a rigorous method of proof for statements about all natural numbers $n = 1, 2, 3, \dots$ .

SchoolThe Principle of Mathematical Induction

Theorem: Principle of mathematical induction

Let $P(n)$ be a statement depending on a positive integer $n$ . If (1) base case: $P(1)$ is true, and (2) inductive step: for every integer $k \ge 1$ , assuming $P(k)$ is true (the inductive hypothesis) implies that $P(k+1)$ is also true, then $P(n)$ is true for all integers $n \ge 1$ .

Why is it true?

From $P(1)$ and the implication $P(1) \Rightarrow P(2)$ we get $P(2)$ ; from $P(2)$ and $P(2) \Rightarrow P(3)$ we get $P(3)$ ; and so on without end, reaching any target integer $n$ in finitely many steps. In axiomatic arithmetic (Peano axioms), induction is one of the defining axioms of the natural numbers.

Proof

Suppose $P(1)$ holds and for every integer $k \ge 1$ , the implication $P(k) \Rightarrow P(k+1)$ holds. To prove that $P(n)$ holds for all $n \ge 1$ , assume for contradiction that the set of counterexamples $S = \{n \in \mathbb{Z}_{\ge 1} : P(n) \text{ is false}\}$ is non-empty.

By the Well-Ordering Principle of the positive integers $\mathbb{Z}_{\ge 1}$ , the non-empty subset $S$ possesses a least element $m = \min S \ge 1$ . Since $P(1)$ is true by the base case hypothesis, we have $1 \notin S$ , which forces $m \ge 2$ and therefore $m - 1 \ge 1$ .

Because $m - 1 < m$ and $m$ is the smallest element of $S$ , we must have $m - 1 \notin S$ , meaning $P(m-1)$ is true. Applying the inductive step with $k = m - 1 \ge 1$ yields $P(m-1) \Rightarrow P(m)$ , so $P(m)$ is true. This contradicts $m \in S$ , proving $S = \varnothing$ and hence $P(n)$ holds for all $n \ge 1$ .

\bigl(P(1) \;\wedge\; \forall k \ge 1,\; (P(k) \Rightarrow P(k+1))\bigr) \;\Longrightarrow\; \forall n \ge 1,\; P(n)

Example: Sum of the first n positive integers

Prove that for every integer $n \ge 1$ , $1 + 2 + \cdots + n = \frac{n(n+1)}{2}$ .

Solution

**Base case ( $n = 1$ ):** The left-hand side is $1$ , and the right-hand side is $\frac{1(1+1)}{2} = 1$ , so $P(1)$ holds.

Inductive step: Assume $P(k)$ holds for some $k \ge 1$ , meaning $1 + 2 + \cdots + k = \frac{k(k+1)}{2}$ . Adding $k + 1$ to both sides gives $1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) = (k+1)\left(\frac{k}{2} + 1\right) = \frac{(k+1)(k+2)}{2}$ , which is $P(k+1)$ . By mathematical induction, the formula holds for all $n \ge 1$ .

\sum_{j=1}^{n} j^2 = 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} = \frac{1}{3}n^3 + \frac{1}{2}n^2 + \frac{1}{6}n

Visualizing discrete sums versus continuous area: adjusting the number of rectangles

n

compares the step-function sum

\sum_{j=1}^{n} j^2 = \frac{n(n+1)(2n+1)}{6}

with the integral

\int_0^n x^2\,dx = \frac{n^3}{3}

, illustrating how each inductive step adds the next bar of area

(k+1)^2

Example: An exponential inequality

Prove that $2^n > n$ for every integer $n \ge 1$ .

Solution

**Base case ( $n = 1$ ):** $2^1 = 2 > 1$ , which is true.

Inductive step: Assume $2^k > k$ for some $k \ge 1$ . Multiplying both sides by $2$ gives $2^{k+1} = 2 \cdot 2^k > 2k = k + k \ge k + 1$ (since $k \ge 1$ ). Therefore $2^{k+1} > k + 1$ , completing the induction.

UndergraduateStrong Induction and the Well-Ordering Principle

Definition: Strong induction (complete induction)

To prove $P(n)$ for all $n \ge n_0$ , it suffices to verify $P(n_0)$ and show that for every $k \ge n_0$ , if $P(n_0), P(n_0+1), \dots, P(k)$ all hold, then $P(k+1)$ holds. Despite its name, strong induction is logically equivalent to ordinary induction: apply ordinary induction to the combined statement $Q(n) = P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ .

Theorem: Principle of strong induction and logical equivalence

Let $P(n)$ be a statement for integers $n \ge n_0$ . If $P(n_0)$ holds and for every integer $k \ge n_0$ , the assumption $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ holds, then $P(n)$ holds for all integers $n \ge n_0$ . Moreover, strong induction, ordinary induction, and the well-ordering principle are logically equivalent.

Why is it true?

Strong induction lets us reach back to any earlier case $P(j)$ with $n_0 \le j \le k$ (such as $a, b \le k$ when factoring $k+1 = a b$ or $P(k-1)$ and $P(k)$ in Fibonacci recurrences) without needing any extra axioms beyond ordinary induction.

Proof

Reduction to ordinary induction: Given a predicate $P(n)$ for $n \ge n_0$ , define the cumulative conjunction $Q(n) \equiv P(n_0) \wedge P(n_0+1) \wedge \cdots \wedge P(n)$ . At the base index $n = n_0$ , the conjunction $Q(n_0)$ has a single term $P(n_0)$ , which holds by the strong base case hypothesis.

**Inductive step for $Q(k)$ :** Fix an integer $k \ge n_0$ and assume $Q(k)$ is true. By definition of $Q(k)$ , all statements $P(n_0), P(n_0+1), \dots, P(k)$ are true. The strong inductive hypothesis $\bigl(P(n_0) \wedge \cdots \wedge P(k)\bigr) \Rightarrow P(k+1)$ then implies that $P(k+1)$ is also true.

Conclusion: Combining $Q(k)$ with $P(k+1)$ proves $Q(k+1) \equiv Q(k) \wedge P(k+1)$ . By the ordinary principle of mathematical induction applied to $Q(n)$ , the statement $Q(n)$ holds for every integer $n \ge n_0$ ; in particular, its last conjunct $P(n)$ holds for all $n \ge n_0$ .

Example: Existence of prime factorizations

Prove that every integer $n \ge 2$ is either a prime or a product of primes.

Solution

**Base case ( $n = 2$ ):** $2$ is prime.

Strong inductive step: Fix $k \ge 2$ and assume every integer $m$ with $2 \le m \le k$ is a prime or a product of primes. Consider $k + 1$ . If $k + 1$ is prime, we are done. Otherwise, $k + 1 = a b$ for integers $a, b$ satisfying $2 \le a, b \le k$ . Ordinary induction cannot help because $a$ and $b$ are not $k$ , only $\le k$ . By the strong inductive hypothesis, both $a$ and $b$ are products of primes, so their product $k + 1 = a b$ is also a product of primes.

Definition: Well-ordering principle

Every non-empty subset $S \subseteq \mathbb{N}$ of the positive integers has a least element $m \in S$ such that $m \le x$ for all $x \in S$ .

Well-ordering, ordinary induction, and strong induction are three faces of the same principle. To deduce induction from well-ordering, suppose $P(1)$ holds and $P(k) \Rightarrow P(k+1)$ for all $k \ge 1$ , yet $P(n)$ fails for some $n$ . Then the set of counterexamples $S = \{n \ge 1 : P(n) \text{ is false}\}$ is non-empty, so by well-ordering it has a smallest element $m$ . We cannot have $m = 1$ because $P(1)$ is true; hence $m - 1 \ge 1$ is not in $S$ , meaning $P(m-1)$ is true. By the inductive step, $P(m)$ must also be true, contradicting $m \in S$ . This phrasing is often called the minimal counterexample method.

AdvancedGeometric Induction: Tiling with Trominoes

Example: Golomb's tromino tiling (1954)

An L-tromino is a tile made of $3$ unit squares in an L-shape. Prove that for every integer $n \ge 1$ , any $2^n \times 2^n$ chessboard with any single square removed can be tiled completely by non-overlapping L-trominoes.

Solution

Notice that strengthening the statement to any missing square (not just a corner) is what makes induction work. **Base case ( $n = 1$ ):** Removing any square from a $2 \times 2$ board leaves an L-shape of $3$ squares, which is covered by $1$ tromino.

Inductive step: Assume the claim holds for $2^k \times 2^k$ boards. Divide a $2^{k+1} \times 2^{k+1}$ board (with one square missing) into four $2^k \times 2^k$ quadrants. The missing square lies in one quadrant. Place a single L-tromino at the center so that its $3$ squares cover one corner square of each of the other three quadrants. Now every $2^k \times 2^k$ quadrant has exactly one unavailable square, so by the inductive hypothesis all four quadrants can be tiled.

ResearchSubtle Pitfalls and Where Induction Stops

Common mistake. Pólya's fallacy: "All horses are the same colour." Let

P(n)

be: in any set of

n

horses, all horses have the same colour. **Base case (

n = 1

): One horse clearly has the same colour as itself. "Inductive step":** Given

k + 1

horses

\{h_1, h_2, \dots, h_{k+1}\}

, the first

k

horses

\{h_1, \dots, h_k\}

share a colour by

P(k)

, and the last

k

horses

\{h_2, \dots, h_{k+1}\}

also share a colour by

P(k)

; since the middle horses

\{h_2, \dots, h_k\}

belong to both groups, all

k + 1

horses must share the same colour! Where is the bug? The implication

P(k) \Rightarrow P(k+1)

fails specifically at

k = 1

: for

k + 1 = 2

horses, the two subsets

\{h_1\}

and

\{h_2\}

have empty intersection

\{h_2, \dots, h_k\} = \varnothing

, so no common horse links their colours.

Why cannot every true statement about integers be proved by simple induction on $n$ ? A striking example is the Collatz conjecture (`collatz-conjecture`, posed in 1937): starting from any positive integer $n$ , repeatedly replace an even number $x$ by $x/2$ and an odd number $x$ by $3x + 1$ ; the conjecture asserts that the trajectory always reaches $1$ . If we try strong induction on $n$ , even numbers $2k$ reduce immediately to $k < 2k$ , which works—but an odd number $2k + 1$ jumps upward to $6k + 4 > 2k + 1$ , outside the range covered by the inductive hypothesis $P(1), \dots, P(2k+1)$ .

In a proof by mathematical induction of a statement $P(n)$ for all $n \ge 1$ , what must the inductive step establish?

Where does Pólya's bogus induction proof that "all horses have the same colour" break down?

How does strong induction differ from ordinary induction?

Why does naive strong induction on $n$ fail to prove the Collatz conjecture?

References

Florian Cajori (1918). Origin of the Name 'Mathematical Induction' · DOI:10.1080/00029890.1918.11998404
Solomon W. Golomb (1954). Checkerboards and Polyominoes · DOI:10.1080/00029890.1954.11988548
David Bařina (2021). Convergence verification of the Collatz problem · DOI:10.1007/s11227-020-03368-x