Induction — Strong vs Weak

Why This Matters

Mathematical induction is the basic tool of finite combinatorics and the natural-number companion to well-ordering. There are two forms a contest writer needs to recognize on sight.

Weak (ordinary) induction. To prove $P(n)$ for all $n \ge n_0$ :

Base: prove $P(n_0)$ .
Step: assume $P(n)$ and prove $P(n + 1)$ .

Strong induction. To prove $P(n)$ for all $n \ge n_0$ :

Base: prove $P(n_0)$ (sometimes several base cases).
Step: assume $P(n_0), P(n_0 + 1), \ldots, P(n)$ and prove $P(n + 1)$ .

Over the natural numbers the two are logically equivalent: each implies the other, and both are equivalent to well-ordering. The choice between them is expository, not logical. Use whichever form makes the inductive step easiest to write.

Strong induction is the right tool when:

The recursive structure depends on more than just the immediate predecessor (e.g., Fibonacci-type recurrences: $a_{n+1}$ depends on $a_n$ and $a_{n-1}$ ).
You decompose a size- $n$ object into pieces of arbitrary smaller sizes (e.g., a polygon triangulated into smaller polygons; an integer factored into smaller integers).
The natural recursion does not preserve the immediate-predecessor shape (e.g., halving arguments: $f(n)$ in terms of $f(\lfloor n/2 \rfloor)$ ).

Weak induction is the right tool when:

The recursive step is genuinely "one more" (sums, products, cardinalities of $\{1, 2, \ldots, n\}$ ).
The inductive hypothesis at $n$ is exactly what you need to produce the hypothesis at $n + 1$ .

Picking the wrong form does not break the proof, but it can double the bookkeeping. A practiced writer notices the recursion structure first and matches the induction form to it.

The Principle Itself

Theorem

The Principle of Mathematical Induction

Statement

If $P(n_0)$ is true and, for every $n \ge n_0$ , $P(n) \Rightarrow P(n + 1)$ , then $P(n)$ is true for every $n \ge n_0$ .

Intuition

The natural numbers are generated by starting at $n_0$ and applying "successor" repeatedly. Induction says: a property that survives both the starting point and the successor step must hold at every reachable element, i.e., every natural number $\ge n_0$ .

Equivalently, induction is the negation-form of well-ordering: if the set of counterexamples were non-empty, well-ordering gives it a smallest element $m$ , then $P(m - 1)$ true (since $m$ is smallest counterexample) plus the inductive step forces $P(m)$ true, contradicting $m$ being a counterexample.

Proof Sketch

Suppose for contradiction that some $m \ge n_0$ has $P(m)$ false. Let $S = \{n \ge n_0 : P(n) \text{ false}\}$ . Then $S \subseteq \mathbb{N}$ and $S$ is non-empty (it contains $m$ ). By well-ordering $S$ has a smallest element $m^*$ .

Since $P(n_0)$ is true, $m^* > n_0$ , so $m^* - 1 \ge n_0$ . Since $m^* - 1 < m^*$ , $m^* - 1 \notin S$ , so $P(m^* - 1)$ is true. By the inductive step, $P(m^*)$ is true. But $m^* \in S$ says $P(m^*)$ is false, a contradiction.

Hence $S$ is empty: $P(n)$ holds for all $n \ge n_0$ .

Why It Matters

The proof above shows that induction follows from well-ordering. The converse also holds: well-ordering follows from induction (plus a routine argument). So the two are logically equivalent. Most working mathematicians treat induction as the primary tool because it gives a procedure ("how do I produce the proof?") rather than just a guarantee ("a smallest element exists").

Failure Mode

Induction over $\mathbb{N}$ does not extend to the reals. " $P(0)$ holds and $P(x) \Rightarrow P(x + 1)$ " does not give $P$ on all reals, only on the natural numbers shifted by 0. Continuous analogs require different machinery (the continuity-based approach to induction over $[0, 1]$ , or the transfinite extension to ordinals). The natural-number structure is essential.

report a correction →

Strong Induction in Action: Prime Factorization

Example

Every integer $n \ge 2$ has a prime factorization

Problem. Show that every integer $n \ge 2$ can be written as a product of primes.

Solution. This is the canonical strong-induction problem. Weak induction does not fit naturally because $n + 1$ does not factor "in terms of" $n$ . It factors in terms of pairs of smaller numbers whose sizes you do not know in advance.

Base. $P(2)$ : 2 is prime, hence a product of primes (a product with one factor).

Inductive step. Assume $P(k)$ holds for every $2 \le k \le n$ ; we show $P(n + 1)$ .

Case 1: $n + 1$ is prime. Then $n + 1$ is itself a product of primes (a one-factor product). $P(n + 1)$ holds.

Case 2: $n + 1$ is composite. Then $n + 1 = a \cdot b$ with $2 \le a, b \le n$ . By the strong inductive hypothesis, both $a$ and $b$ have prime factorizations. Concatenating the two gives a prime factorization of $n + 1$ .

In both cases $P(n + 1)$ holds. By strong induction, every $n \ge 2$ has a prime factorization.

Notice that weak induction would not have given access to $P(a)$ and $P(b)$ ; it only gives $P(n)$ , and there is no natural way to extract $a$ or $b$ from $n + 1$ at the rate of "one less". Strong induction is essential.

Weak Induction in Action: Sum of First $n$ Squares

Example

Sum of the first n squares

Problem. Show $1^2 + 2^2 + \cdots + n^2 = \frac{n(n + 1)(2n + 1)}{6}$ for every $n \ge 1$ .

Solution. Weak induction fits naturally because the LHS at $n + 1$ is exactly LHS-at- $n$ plus $(n+1)^2$ .

Base. $n = 1$ : LHS $= 1$ , RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$ . ✓

Inductive step. Assume $\sum_{k=1}^n k^2 = \frac{n(n + 1)(2n + 1)}{6}$ . Add $(n + 1)^2$ to both sides: $\sum_{k=1}^{n+1} k^2 = \frac{n(n + 1)(2n + 1)}{6} + (n + 1)^2 = \frac{(n + 1) [n(2n + 1) + 6(n + 1)]}{6} = \frac{(n + 1)(n + 2)(2n + 3)}{6}.$ This matches the formula at $n + 1$ . ✓

By weak induction the formula holds for every $n \ge 1$ .

Strong induction would work here too but is overkill: only $P(n)$ enters the step, never $P(n - 1)$ or earlier.

When the Two Forms Look Very Different

Example

Triangulations of a convex polygon

Problem. Show that every triangulation of a convex $n$ -gon (using only diagonals between vertices) has exactly $n - 2$ triangles, for $n \ge 3$ .

Strong-induction solution. Pick any diagonal in the triangulation; it splits the polygon into a $k$ -gon and an $(n - k + 2)$ -gon, both convex and both triangulated by the diagonals of the original triangulation that fall on each side. By the strong inductive hypothesis the two sub-polygons contribute $(k - 2) + ((n - k + 2) - 2) = n - 2$ triangles.

If there are no diagonals (only possible when $n = 3$ ), the polygon is a single triangle: $1 = 3 - 2$ . ✓

Weak-induction solution. Try to set up a proof where $P(n) \Rightarrow P(n + 1)$ . The issue: a triangulation of an $(n + 1)$ -gon does not naturally come with an embedded triangulation of an $n$ -gon. You can construct one (cut off an "ear", a triangle bounded by two adjacent sides of the polygon), but every triangulation has at least two ears, so the cut is non-canonical. The argument is more awkward.

The strong form is easier because the natural recursion is "split into two pieces of arbitrary sizes summing to $n + 2$ ", not "remove one piece of size 1".

Common Mistakes

Watch Out

Forgetting the base case

The inductive step alone proves nothing. Without a base case, " $P(n) \Rightarrow P(n + 1)$ " can hold for an entirely false property: e.g., $P(n)$ = " $n^2 + n + 41$ is composite" satisfies the implication trivially when both $P(n)$ and $P(n + 1)$ are false, but the property is also false for small $n$ . The base case is what anchors the chain to reality.

Watch Out

Multiple base cases for strong induction

Strong induction with a recursion of depth $d$ (e.g., $a_{n+1} = a_n + a_{n - 1}$ has depth 2) needs $d$ base cases, not 1. Forgetting this is the most common error in Fibonacci-type problems. Check: when you write the inductive step at the smallest $n$ where it applies, do all the hypotheses you need actually exist? If the step at $n + 1$ uses $P(n)$ and $P(n - 1)$ , then you need $P(n_0)$ and $P(n_0 + 1)$ as base cases.

Watch Out

Off-by-one on the hypothesis

The inductive hypothesis at $n$ gives you $P(n)$ , not $P(n + 1)$ . A common pattern: the writer assumes " $P(n)$ " but uses a fact that requires $P(n + 1)$ in disguise. Re-read the step and check that every appeal to the hypothesis really does use $P(n)$ (or, in strong induction, $P(k)$ for some $k \le n$ ).

Watch Out

Inducting on the wrong variable

Many problems have multiple natural integer parameters. Picking the wrong one to induct on can make the step impossible. Example: a problem about $m \times n$ grids may need induction on $m + n$ , not on $m$ alone or $n$ alone. If your induction seems to stall, try a different inductive parameter.

Watch Out

Reverse induction is a separate technique

Cauchy's proof of AM-GM uses reverse induction: prove $P(n)$ for $n$ a power of 2, then "fill in" by showing $P(n + 1) \Rightarrow P(n)$ . This is a valid technique but it is not ordinary induction; treating it as such confuses the direction of implication.

Exercises

ExerciseCore

Problem

Show by induction that $1 + 3 + 5 + \cdots + (2n - 1) = n^2$ for every $n \ge 1$ . Decide whether weak or strong induction is the natural fit, and justify briefly.

ExerciseCore

Problem

Show by strong induction that every postage of $n \ge 8$ cents can be made using only 3-cent and 5-cent stamps.

ExerciseAdvanced

Problem

Define the Fibonacci numbers by $F_1 = F_2 = 1$ and $F_{n + 1} = F_n + F_{n - 1}$ for $n \ge 2$ . Show that $\gcd(F_n, F_{n + 1}) = 1$ for every $n \ge 1$ .

Cross-Network Links

ProofsPath: induction-on-non-natural-orderings extends induction to any well-founded order: trees, ordinals, pairs $(m, n)$ with lex order; well-ordering-principle is the equivalent foundation; proof-by-infinite-descent is induction in negative disguise; pigeonhole-principle-elementary pairs with induction on the size of a finite set.
TheoremPath: measure-theoretic-probability uses transfinite induction for the construction of Borel sets; maximum-likelihood-estimation uses induction on sample size in some asymptotic proofs.
ComputationPath: structural induction on syntax trees and inductive types is the operational form of mathematical induction in proof assistants.

References

See structured references block. Primary entry points: Velleman How to Prove It Ch 6 for the technique with worked examples; Engel Problem-Solving Strategies Ch 1 for olympiad-flavored applications; Knuth TAOCP Vol 1 §1.2.1 for the algorithmic form (loop invariants are induction in disguise); Halmos Naive Set Theory §12 for the foundational construction.

Induction — Strong vs Weak

Induction — Strong vs Weak

Why This Matters

The Principle Itself

Strong Induction in Action: Prime Factorization

Weak Induction in Action: Sum of First nnn Squares

When the Two Forms Look Very Different

Common Mistakes

Exercises

Cross-Network Links

References

Weak Induction in Action: Sum of First $n$ Squares