maths2u
PhysicsMathsChemistryBiology
Tier
⌕ Search ⌘K
Theorem

The principle of mathematical induction

T-001Home MU-101Threads logic · structure
Statement

Let \( \mathbb{N} = \{1, 2, 3, \dots\} \) denote the natural numbers, equipped with their usual order, and let \( P(n) \) be a predicate — a property that is either true or false for each \( n \in \mathbb{N} \), with no ambiguity. Suppose that (i) base case: \( P(1) \) is true, and (ii) inductive step: for every \( n \in \mathbb{N} \), if \( P(n) \) is true then \( P(n+1) \) is true; symbolically, \( \forall n \in \mathbb{N},\; P(n) \Rightarrow P(n+1) \). Then \( P(n) \) is true for every \( n \in \mathbb{N} \): \( \forall n \in \mathbb{N},\; P(n) \). We prove this from the Well-Ordering Principle (every non-empty subset of \( \mathbb{N} \) has a least element) together with the Predecessor Lemma (every natural number other than \( 1 \) is of the form \( k+1 \) for some \( k \in \mathbb{N} \)); in axiomatic developments following Peano, induction is instead taken as an axiom and well-ordering is derived from it.

Why it matters

Induction is the fundamental proof technique for statements indexed by the natural numbers, and it is the engine behind recursive definition: without it we could not legitimately define \( n! \), \( a^n \), the Fibonacci numbers, or prove that such definitions determine a unique function. Nearly every closed-form identity, divisibility fact, growth estimate, and algorithmic correctness argument in a first-year course rests on it.

Conceptually, induction is what distinguishes \( \mathbb{N} \) from other ordered systems: it encodes the fact that the naturals are generated from \( 1 \) by repeated succession, with nothing extra. Its generalisations — strong induction, structural induction, transfinite induction, well-founded induction — carry this generative principle into algebra, logic, computer science, and set theory.

Hypotheses
Hypothesis. Base case \( P(1) \).Drop it and the theorem fails: let \( P(n) \) be the statement "\( n \geq 2 \)". The inductive step holds (if \( n \geq 2 \) then \( n+1 \geq 2 \)), but \( P(1) \) is false, and indeed \( P \) does not hold for all \( n \) — it fails at \( n = 1 \). An inductive step with nothing to start from proves nothing. Inductive step for every \( n \in \mathbb{N} \).Let \( P(n) \) be "\( n \leq 3 \)". Then \( P(1) \) holds and \( P(n) \Rightarrow P(n+1) \) holds for \( n = 1, 2 \), but fails at \( n = 3 \); the conclusion fails at \( n = 4 \). A single missing rung breaks the whole ladder — the step must be verified for arbitrary \( n \), not just small ones. The index set is \( \mathbb{N} \) (well-ordered, generated by succession).On \( \mathbb{Q}_{\geq 0} \) or \( \mathbb{R} \) the argument collapses: "\( x \) is an integer" holds at \( 1 \) and is preserved by \( x \mapsto x + 1 \), yet certainly not every real is an integer. Stepping by \( +1 \) does not exhaust a set that is not generated from \( 1 \) by succession. \( P \) is a genuine predicate: for each \( n \), \( P(n) \) has a determinate truth value.The sorites "paradox" abuses this: with the vague property "\( n \) grains of sand do not form a heap", the base case is plausible and the step "one more grain never creates a heap" is plausible, yet the conclusion is absurd. The fault is not with induction but with the fact that "heap" is not a well-defined predicate on \( \mathbb{N} \). In formal treatments \( P \) must be a formula of the ambient language (first-order schema) or an arbitrary subset of \( \mathbb{N} \) (second-order axiom) — and the two choices are not equivalent in strength.
Proof
1
Assume (i) and (ii). Define \( S = \{\, n \in \mathbb{N} : P(n) \text{ is false} \,\} \subseteq \mathbb{N} \). The theorem asserts exactly that \( S = \emptyset \).
Legal by comprehension: \( S \) is a well-defined subset of \( \mathbb{N} \) because \( P \) is a genuine predicate. Reformulating "for all \( n \), \( P(n) \)" as "\( S = \emptyset \)" is pure logic. A
2
Suppose, for contradiction, that \( S \neq \emptyset \). Then \( S \) has a least element \( m \): \( m \in S \) and \( \forall k \in S,\; m \leq k \).
Well-Ordering Principle: every non-empty subset of \( \mathbb{N} \) has a least element. This is the axiom of the number system on which the entire proof pivots. B
3
\[ m \neq 1. \quad \text{Indeed } P(1) \text{ holds by hypothesis (i), so } 1 \notin S. \]
Direct application of the base case (i) and the definition of \( S \) from Step 1. A
4
\[ \text{Since } m \in \mathbb{N} \text{ and } m \neq 1, \text{ there exists } k \in \mathbb{N} \text{ with } m = k + 1; \text{ write } k = m - 1 \in \mathbb{N}. \]
Predecessor Lemma: every element of \( \mathbb{N} \) is either \( 1 \) or a successor. This is not free: in a Peano-style development it is proved by induction itself (so there we must argue in the other direction, deriving well-ordering from induction); in the set-theoretic construction of \( \mathbb{N} \) as the least inductive set, it is proved directly from minimality of \( \mathbb{N} \) among inductive sets. We cite it as an established structural fact of the number system, on par with well-ordering. Omitting to justify this step is the classic hidden gap in textbook proofs. C
5
\[ m - 1 \lt m, \quad \text{so } m - 1 \notin S \text{ by minimality of } m; \quad \text{hence } P(m-1) \text{ is true.} \]
\( m - 1 \lt m \) is immediate from the order axioms (\( k \lt k+1 \) for all \( k \)). If \( m-1 \) were in \( S \), it would be an element of \( S \) strictly smaller than the least element \( m \) — contradiction. So \( m - 1 \notin S \), which by definition of \( S \) means \( P(m-1) \) holds. B
6
\[ \text{Apply hypothesis (ii) with } n = m-1: \quad P(m-1) \Rightarrow P(m). \quad \text{Hence } P(m) \text{ is true.} \]
The inductive step (ii) is a universally quantified implication over all of \( \mathbb{N} \); Step 4 established \( m - 1 \in \mathbb{N} \), so instantiating at \( n = m-1 \) is legitimate, and modus ponens with Step 5 yields \( P(m) \). B
7
\[ P(m) \text{ true} \;\Rightarrow\; m \notin S. \quad \text{But } m \in S \text{ by Step 2 — contradiction.} \]
Definition of \( S \) again. The assumption \( S \neq \emptyset \) has produced a contradiction, so by reductio ad absurdum \( S = \emptyset \). A
8
\[ S = \emptyset, \quad \text{i.e.} \quad \forall n \in \mathbb{N},\; P(n). \qquad \blacksquare \]
Unwinding Step 1: the emptiness of the counterexample set is precisely the conclusion of the theorem. A
Result
\[ \Big( P(1) \;\wedge\; \forall n \in \mathbb{N}\,\big(P(n) \Rightarrow P(n+1)\big) \Big) \;\Longrightarrow\; \forall n \in \mathbb{N},\; P(n) \]

Reading. To prove infinitely many statements \( P(1), P(2), P(3), \dots \) it suffices to do two finite things: check the first one, and show that each one hands its truth on to the next. The ladder metaphor is exact — you can reach the first rung, and from any rung you can reach the next, so you can reach every rung.

Scope. Applies to any genuine predicate over \( \mathbb{N} \) (or, by relabelling, over \( \{n \in \mathbb{Z} : n \geq n_0\} \) for any fixed integer \( n_0 \), with base case \( P(n_0) \)). It does not apply to \( \mathbb{Z} \), \( \mathbb{Q} \), or \( \mathbb{R} \) as index sets, and it proves \( P(n) \) for each finite \( n \) — it says nothing about any "limiting" or "infinite" statement such as \( \lim_{n \to \infty} \) of some quantity, which requires separate argument.

Corollaries & converses
  • Shifted base. If \( P(n_0) \) holds and \( P(n) \Rightarrow P(n+1) \) for all \( n \geq n_0 \), then \( P(n) \) holds for all integers \( n \geq n_0 \). (Apply the theorem to \( Q(k) = P(n_0 + k - 1) \).)
  • Strong (complete) induction. If for every \( n \), \( \big(\forall k \lt n,\; P(k)\big) \Rightarrow P(n) \), then \( P(n) \) holds for all \( n \). Derived by applying ordinary induction to \( Q(n) = \big(P(1) \wedge \dots \wedge P(n)\big) \); note no separate base case is needed, since at \( n = 1 \) the hypothesis is vacuous. (See Problem 4 for the technique in action.)
  • Well-Ordering Principle. Conversely, induction implies well-ordering (Problem 5), so — granted the Predecessor Lemma — the two principles are equivalent over the remaining axioms of arithmetic.
  • Principle of recursive definition. Given \( a \in X \) and \( f : X \to X \), there is a unique sequence \( (x_n) \) with \( x_1 = a \) and \( x_{n+1} = f(x_n) \). Uniqueness is immediate by induction; existence requires a separate (and often glossed-over) argument, the Dedekind recursion theorem.
  • Converse of the theorem. The converse holds, trivially: if \( P(n) \) is true for all \( n \), then \( P(1) \) is true and every implication \( P(n) \Rightarrow P(n+1) \) has a true consequent, hence is true. So the two hypotheses are jointly equivalent to the conclusion — induction is precisely a reduction of one infinite verification to two manageable ones.
Fails without
  • No base case. \( P(n) \): "\( n = n + 1 \)". The inductive step is valid: if \( n = n+1 \), adding \( 1 \) to both sides gives \( n + 1 = n + 2 \). Yet \( P(n) \) is false for every \( n \). Vacuously true steps cost nothing — the base case is what injects actual truth into the chain.
  • Inductive step checked only for some \( n \). \( P(n) \): "\( n^2 - n + 41 \) is prime" (Euler). True for \( n = 1, 2, \dots, 40 \) — forty consecutive verifications — yet false at \( n = 41 \), where \( 41^2 - 41 + 41 = 41^2 \). No amount of case-checking substitutes for a proof of the step at arbitrary \( n \).
  • Index set not \( \mathbb{N} \). On \( \mathbb{Z} \), take \( P(n) \): "\( n \geq 1 \)". Base \( P(1) \) holds; step \( n \geq 1 \Rightarrow n+1 \geq 1 \) holds for all integers \( n \); but \( P(0) \) is false. Succession from \( 1 \) never reaches the integers below the base point, and \( \mathbb{Z} \) is not well-ordered, so the proof's appeal to a least counterexample is unavailable.
  • Predicate not well-defined. The sorites argument ("adding one grain never makes a heap") has a plausible base and step but an absurd conclusion — diagnosing exactly which hypothesis fails (the predicate is vague, so there is no set \( S \) of counterexamples to well-order) is a genuine exercise in reading the theorem's fine print.
Common errors
  • Assuming the conclusion. Writing "assume \( P(n) \) holds for all \( n \)" in the inductive step. The inductive hypothesis is \( P(n) \) for one arbitrary fixed \( n \); assuming it for all \( n \) is assuming the theorem you are trying to prove.
  • The all-horses-are-the-same-colour fallacy (Pólya). The "proof" that any \( n \) horses share a colour has a valid-looking step: remove one horse, apply the hypothesis, remove another, apply it again, and let the overlap force equality. The step genuinely works for \( n \geq 2 \Rightarrow n+1 \) — but fails at \( n = 1 \Rightarrow 2 \), because two sets of one horse each need not overlap. Moral: verify the step at its first application, where degenerate configurations live.
  • Wrong direction. Proving \( P(n+1) \Rightarrow P(n) \). This is downward induction and, from base case \( P(1) \), proves nothing about \( n \geq 2 \).
  • Starting the algebra from the target. In identity proofs, beginning with the claimed equation for \( n+1 \) and manipulating both sides until something true appears. Unless every step is visibly reversible, this proves the converse of what is needed. Start from one side (or from the inductive hypothesis) and derive the other.
  • Base case at the wrong point. Proving \( P(1) \) when the step \( P(n) \Rightarrow P(n+1) \) is only valid for \( n \geq 5 \) (as in \( 2^n \gt n^2 \)): the chain from \( 1 \) breaks before the step becomes usable. Base case and step must meet: the base must be at (or before) the first \( n \) for which the step applies, and cover any gap by direct verification.
  • Believing induction proves a statement "at infinity". Induction shows \( P(n) \) for each natural \( n \); it does not show that a limiting object has the property. Each set \( \{1, \dots, n\} \) is finite, but \( \mathbb{N} \) is not; each partial sum \( \sum_{k=1}^{n} \frac{1}{k} \) is finite, but the series diverges.
Discussion

Traces of inductive reasoning appear in Euclid (the infinitude of primes) and in medieval mathematics (al-Karaji, Levi ben Gershon), but the first reasonably explicit uses are usually credited to Maurolico (1575) and Pascal, whose Traité du triangle arithmétique (1665) proves properties of the binomial coefficients by an unmistakable base-and-step argument. The principle was isolated as a foundational axiom in the nineteenth century: Dedekind's Was sind und was sollen die Zahlen? (1888) derived it from his analysis of "chains", and Peano (1889) enshrined it as the fifth of his axioms for arithmetic. Which of induction and well-ordering is the "axiom" and which the "theorem" is thus a matter of where one starts: analysis texts often posit well-ordering and prove induction (as we did), while logic texts posit induction and prove well-ordering (Problem 5).

The equivalence just mentioned deserves care. Ordinary induction, strong induction, and well-ordering are interderivable, but only in the presence of background structure — notably the Predecessor Lemma of Step 4 and basic order axioms. Over weaker base theories the three can come apart, which is why a rigorous course fixes an axiomatisation first and derives the others as theorems, rather than treating them as interchangeable folklore.

The principle generalises far beyond \( \mathbb{N} \). Transfinite induction extends it to any well-ordered set, and in particular to the ordinals: if the truth of \( P \) below \( \alpha \) always forces \( P(\alpha) \), then \( P \) holds at every ordinal — the successor/limit case split replacing the single \( n \mapsto n+1 \) step. Structural induction, ubiquitous in logic and computer science, proves properties of formulas, trees, and programs by induction on their construction. All are instances of one master principle, well-founded induction: on any set with a relation admitting no infinite descending chains, a property that propagates from all predecessors to each element holds everywhere.

A sharper foundational point: Peano's original induction axiom is second-order — it quantifies over all subsets of \( \mathbb{N} \) — and (with the other axioms) pins down \( \mathbb{N} \) uniquely up to isomorphism (Dedekind's categoricity theorem). First-order Peano arithmetic (PA) can only approximate this with an axiom schema: one induction axiom per formula. Since there are countably many formulas but uncountably many subsets, the schema is strictly weaker: by compactness, PA has nonstandard models containing "infinite" elements beyond every standard natural, in which every instance of the schema still holds. Concrete casualties of this weakness exist: Goodstein's theorem and the Paris–Harrington theorem are true statements about \( \mathbb{N} \), provable via ordinal induction up to \( \varepsilon_0 \), but unprovable in PA (Kirby–Paris, 1982). Induction is not one principle but a calibrated hierarchy, and measuring exactly how much induction a theorem needs is the subject of reverse mathematics and proof theory.

Common misconceptions. Induction is not "assuming what you want to prove": the inductive hypothesis concerns a single arbitrary \( n \), and the step proves an implication, not \( P(n) \) itself. It is not an empirical extrapolation from examples — the Euler polynomial \( n^2 - n + 41 \) and Fermat's numbers \( 2^{2^n} + 1 \) (prime for \( n \leq 4 \), composite at \( n = 5 \)) show verification, however extensive, is not proof. And it establishes each \( P(n) \) for finite \( n \) only; no conclusion "at \( n = \infty \)" is licensed.

Worked examples

Example 1 (Gauss summation). For every \( n \in \mathbb{N} \), \( \displaystyle\sum_{k=1}^{n} k = \frac{n(n+1)}{2} \).

1
\[ \text{Let } P(n) \text{ be the statement } \sum_{k=1}^{n} k = \frac{n(n+1)}{2}. \]
Fix the predicate precisely before anything else; \( P(n) \) is a determinate equality of rationals for each \( n \). A
2
\[ \textbf{Base case:}\quad \sum_{k=1}^{1} k = 1 = \frac{1 \cdot 2}{2}, \quad \text{so } P(1) \text{ holds.} \]
Direct computation. A
3
\[ \textbf{Inductive step:}\quad \text{fix } n \in \mathbb{N} \text{ and assume } P(n): \; \sum_{k=1}^{n} k = \frac{n(n+1)}{2}. \]
This is the inductive hypothesis for one arbitrary fixed \( n \) — not for all \( n \). A
4
\[ \sum_{k=1}^{n+1} k = \left( \sum_{k=1}^{n} k \right) + (n+1) = \frac{n(n+1)}{2} + (n+1) = (n+1)\left( \frac{n}{2} + 1 \right) = \frac{(n+1)(n+2)}{2}. \]
Peel off the last term (associativity of finite sums), substitute the inductive hypothesis, and factor. The final expression is exactly \( P(n+1) \), so \( P(n) \Rightarrow P(n+1) \). B
5
\[ \text{By T-001, } P(n) \text{ holds for all } n \in \mathbb{N}. \]
Both hypotheses of the principle of induction are verified (Steps 2 and 4); the theorem delivers the universal conclusion. A
\[ \forall n \in \mathbb{N}: \quad \sum_{k=1}^{n} k = \frac{n(n+1)}{2} \]

Reading. Two finite checks — one computation and one algebraic implication — certify infinitely many identities at once.

Example 2 (Bernoulli's inequality). Fix a real \( x \geq -1 \). Then \( (1+x)^n \geq 1 + nx \) for every \( n \in \mathbb{N} \).

1
\[ \text{Fix } x \geq -1 \text{ once and for all; let } P(n) \text{ be } (1+x)^n \geq 1 + nx. \]
The induction is on \( n \) only; \( x \) is a parameter frozen before the induction begins. Confusing the roles of \( n \) and \( x \) is a standard blunder. A
2
\[ \textbf{Base case:}\quad (1+x)^1 = 1 + 1 \cdot x, \quad \text{so } P(1) \text{ holds (with equality).} \]
Direct computation. A
3
\[ \textbf{Inductive step:}\quad \text{assume } (1+x)^n \geq 1 + nx \text{ for a fixed } n \in \mathbb{N}. \text{ Since } x \geq -1,\; 1 + x \geq 0. \]
The hypothesis \( x \geq -1 \) enters here and only here: it makes the factor \( 1+x \) non-negative, which is what licenses multiplying an inequality through by it in the next step. B
4
\[ (1+x)^{n+1} = (1+x)^n (1+x) \geq (1 + nx)(1 + x) \]
Multiply both sides of the inductive hypothesis by \( 1 + x \geq 0 \); the order axiom "\( a \geq b,\ c \geq 0 \Rightarrow ac \geq bc \)" requires exactly this sign condition. For \( x \lt -1 \) the factor \( 1+x \) is negative, multiplying by it reverses the inequality, and the theorem itself fails: at \( x = -4 \), \( n = 3 \) we get \( (1+x)^3 = (-3)^3 = -27 \lt -11 = 1 + 3x \). C
5
\[ (1 + nx)(1 + x) = 1 + (n+1)x + n x^2 \geq 1 + (n+1)x, \quad \text{since } n x^2 \geq 0. \]
Expand and discard the non-negative term \( n x^2 \) (squares are non-negative in any ordered field). Chaining Steps 4 and 5 by transitivity of \( \geq \) yields \( P(n+1) \). B
6
\[ \text{By T-001, } (1+x)^n \geq 1 + nx \text{ for all } n \in \mathbb{N}. \]
Base case and inductive step verified; the principle of induction concludes. Since \( x \geq -1 \) was arbitrary, the result holds for every such \( x \). A
\[ \forall x \geq -1,\; \forall n \in \mathbb{N}: \quad (1+x)^n \geq 1 + nx \]

Reading. Compound growth beats linear growth from the same rate — the workhorse inequality behind \( \lim_{n \to \infty} \left(1 + \frac{1}{n}\right)^n = e \), root and ratio estimates, and the unboundedness of geometric sequences with ratio greater than \( 1 \).

Problems
  1. Prove that \( \displaystyle\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} \) for every \( n \in \mathbb{N} \).
    Solution

    Let \( P(n) \) be the stated identity. Base: \( \sum_{k=1}^{1} k^2 = 1 = \frac{1 \cdot 2 \cdot 3}{6} \), so \( P(1) \) holds. Step: assume \( P(n) \) for a fixed \( n \). Then

    \[ \sum_{k=1}^{n+1} k^2 = \frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\big[ n(2n+1) + 6(n+1) \big]}{6} = \frac{(n+1)(2n^2 + 7n + 6)}{6}. \]

    Factorising \( 2n^2 + 7n + 6 = (n+2)(2n+3) \) gives

    \[ \sum_{k=1}^{n+1} k^2 = \frac{(n+1)(n+2)(2n+3)}{6} = \frac{(n+1)\big((n+1)+1\big)\big(2(n+1)+1\big)}{6}, \]

    which is \( P(n+1) \). By T-001, \( P(n) \) holds for all \( n \in \mathbb{N} \).

  2. Prove that \( 3 \) divides \( 4^n - 1 \) for every \( n \in \mathbb{N} \).
    Solution

    Let \( P(n) \): "\( \exists q \in \mathbb{Z} \) with \( 4^n - 1 = 3q \)". Base: \( 4^1 - 1 = 3 = 3 \cdot 1 \). Step: assume \( 4^n - 1 = 3q \) for some integer \( q \). Then

    \[ 4^{n+1} - 1 = 4 \cdot 4^n - 1 = 4(4^n - 1) + 3 = 4 \cdot 3q + 3 = 3(4q + 1), \]

    and \( 4q + 1 \in \mathbb{Z} \), so \( P(n+1) \) holds. By T-001, \( 3 \mid 4^n - 1 \) for all \( n \). (Structurally this is the induction hiding inside the congruence argument \( 4 \equiv 1 \pmod 3 \Rightarrow 4^n \equiv 1^n \pmod 3 \): the rule \( a \equiv b \Rightarrow a^n \equiv b^n \) is itself proved by induction.)

  3. Prove that \( 2^n \gt n^2 \) for every integer \( n \geq 5 \). Explain why the base case cannot be taken at \( n = 1 \).
    Solution

    Let \( P(n) \): "\( 2^n \gt n^2 \)", for \( n \geq 5 \) (shifted-base corollary of T-001). Base: \( 2^5 = 32 \gt 25 = 5^2 \). Step: assume \( 2^n \gt n^2 \) for a fixed \( n \geq 5 \). Then

    \[ 2^{n+1} = 2 \cdot 2^n \gt 2 n^2. \]

    It remains to show \( 2n^2 \geq (n+1)^2 \) for \( n \geq 5 \). Indeed

    \[ 2n^2 - (n+1)^2 = n^2 - 2n - 1 = (n-1)^2 - 2 \geq 4^2 - 2 = 14 \gt 0 \quad \text{for } n \geq 5. \]

    By transitivity \( 2^{n+1} \gt (n+1)^2 \), i.e. \( P(n+1) \). By induction with shifted base, \( P(n) \) holds for all \( n \geq 5 \).

    The base cannot sit at \( n = 1 \): the statement itself is false at \( n = 2, 3, 4 \) (e.g. \( 2^3 = 8 \lt 9 = 3^2 \), \( 2^4 = 16 = 4^2 \) fails strictness), so no chain of implications from \( P(1) \) can be valid through those values — the inductive step \( 2n^2 \geq (n+1)^2 \) genuinely fails for \( n = 2 \): \( 8 \lt 9 \). Base case and step must be verified on the same range.

  4. Using ordinary induction (T-001) — not strong induction as a black box — prove that every integer \( n \geq 2 \) is a product of (one or more) primes.
    Solution

    The trick is to strengthen the predicate. Let \( Q(n) \), for \( n \in \mathbb{N} \), be: "every integer \( m \) with \( 2 \leq m \leq n + 1 \) is a product of primes". We prove \( Q(n) \) for all \( n \) by T-001; the target statement follows since every \( m \geq 2 \) satisfies \( 2 \leq m \leq m \), i.e. is covered by \( Q(m-1) \).

    Base: \( Q(1) \) says every \( m \) with \( 2 \leq m \leq 2 \) is a product of primes; \( 2 \) is prime, so this holds.

    Step: assume \( Q(n) \). To prove \( Q(n+1) \) we must show every \( m \) with \( 2 \leq m \leq n+2 \) is a product of primes. For \( m \leq n+1 \) this is the hypothesis \( Q(n) \). For \( m = n + 2 \): either \( n+2 \) is prime (done, a one-factor product), or \( n + 2 = ab \) with \( 2 \leq a, b \leq n+1 \) (by definition of compositeness, both factors are proper, hence at least \( 2 \) and at most \( \frac{n+2}{2} \leq n+1 \)). By \( Q(n) \), each of \( a, b \) is a product of primes; concatenating the factorisations exhibits \( n+2 \) as a product of primes. Hence \( Q(n+1) \).

    By T-001, \( Q(n) \) holds for all \( n \in \mathbb{N} \), and the claim follows. This bootstrap — inducting on "all values up to \( n \)" — is exactly the proof that strong induction is a corollary of ordinary induction.

  5. (Converse direction of the equivalence.) Assuming the principle of mathematical induction, prove the Well-Ordering Principle: every non-empty subset \( S \subseteq \mathbb{N} \) has a least element.
    Solution

    We prove the contrapositive: if \( S \subseteq \mathbb{N} \) has no least element, then \( S = \emptyset \).

    Let \( P(n) \) be the statement: "no element of \( S \) is \( \leq n \)", i.e. \( S \cap \{1, 2, \dots, n\} = \emptyset \).

    Base: suppose \( 1 \in S \). Since \( 1 \leq k \) for every \( k \in \mathbb{N} \) (an order axiom of \( \mathbb{N} \)), \( 1 \) would be a least element of \( S \), contradicting the assumption. So \( 1 \notin S \), which is \( P(1) \).

    Step: assume \( P(n) \): \( S \cap \{1, \dots, n\} = \emptyset \). Suppose \( n + 1 \in S \). Any element \( s \in S \) satisfies \( s \gt n \) (by \( P(n) \)), hence \( s \geq n + 1 \) (there are no naturals strictly between \( n \) and \( n+1 \) — a structural fact equivalent to the Predecessor Lemma). Then \( n+1 \) would be a least element of \( S \), a contradiction. So \( n + 1 \notin S \), and combined with \( P(n) \) this gives \( S \cap \{1, \dots, n+1\} = \emptyset \), which is \( P(n+1) \).

    By induction, \( P(n) \) holds for every \( n \). Now if \( s \in S \) then taking \( n = s \) in \( P(s) \) gives \( s \notin S \) — contradiction. Hence \( S = \emptyset \), completing the contrapositive. Together with the proof of T-001 from well-ordering, this establishes the equivalence of the two principles (over the order and predecessor axioms used in both directions).