Questions: Strong Induction and the Well-Ordering Principle

Question 1

You want to prove that every integer n ≥ 2 has a prime factorization. The inductive step considers n+1: if it is composite, it factors as a·b where 2 ≤ a, b < n+1. Why does ordinary induction fail here?

• A. Ordinary induction only works for statements about odd numbers
• B. The inductive step needs the hypothesis for both a and b, which may both be less than n — ordinary induction only provides P(n), not P(a) and P(b) for arbitrary a, b < n
• C. Ordinary induction cannot handle proofs about prime numbers
• D. The base case n=2 is too simple to anchor an inductive proof

Answer: (B)

Ordinary induction's inductive step is 'assume P(n), prove P(n+1).' For prime factorization, when n+1 = a·b, we need to know both a and b already have prime factorizations — but a and b could be anywhere from 2 to n, not necessarily equal to n. Strong induction solves this by assuming P(k) holds for ALL k from 1 to n, making the hypothesis available for any value smaller than n+1, not just n.

Question 2

A proof about a sequence defined by S(n) = S(n−1) + S(n−2) begins with 'Assume P(k) for all 1 ≤ k ≤ n, then prove P(n+1).' The author establishes only P(1) as a base case. What is wrong?

• A. Strong induction does not require a base case at all
• B. The inductive step for n+1 requires P(n) and P(n−1); when n=1, P(n−1) = P(0) is not covered by the base case P(1)
• C. The inductive hypothesis should assume P(n) only, not all k ≤ n
• D. The proof is fine — one base case is always sufficient for strong induction

Answer: (B)

The recurrence S(n) = S(n−1) + S(n−2) requires two previous values. When proving P(2) in the inductive step, you need P(1) and P(0) — but P(0) was never established. The fix is to prove both P(1) and P(2) as base cases. Strong induction's guarantee only applies after the base cases fully cover the range the inductive step assumes — the framework is vacuous without the foundation.

Question 3

Strong induction and the well-ordering principle are logically equivalent — neither can prove anything the other cannot.

• T. True
• F. False

Answer: True

The Explainer states this explicitly: 'The two methods — strong induction and well-ordering — are logically equivalent; each can be derived from the other.' Strong induction is often more convenient for building sequences step by step; well-ordering is often cleaner for 'assume a smallest counterexample' arguments. But they are not different in power — any proof using one can in principle be rewritten using the other.

Question 4

Strong induction is strictly more powerful than ordinary induction because it assumes more in the inductive hypothesis.

• T. True
• F. False

Answer: False

Assuming more in the inductive hypothesis makes strong induction more *convenient*, not more *powerful*. Both methods are logically equivalent to the well-ordering principle and can prove exactly the same set of theorems. When a proof uses strong induction with a richer hypothesis, it could in principle be reformulated using ordinary induction (though perhaps less naturally). The extra assumption is a convenience for structuring the argument, not additional logical reach.

Question 5

Why is a well-ordering proof sometimes described as arguing from a 'minimal counterexample'? What role does the well-ordering principle play?

Model answer: To prove P(n) for all n ∈ ℕ using well-ordering, assume for contradiction that some n fails P(n). The set of all such failures is non-empty, so by the well-ordering principle it has a minimum element n₀ — the smallest counterexample. The proof then derives a contradiction: either P(n₀) must hold after all, or a smaller counterexample can be constructed, both contradicting the minimality. The well-ordering principle guarantees that a smallest failure exists if any failure exists, which is the anchor the contradiction argument needs.

The well-ordering principle is not just 'lists have minimums' — it is a proof engine. It converts 'there exists a counterexample' into 'there exists a MINIMAL counterexample,' which is a much stronger and more tractable object to work with. This is why proofs using this method often feel like 'if it failed somewhere, it must fail here for the first time, but that leads to a contradiction.' Without well-ordering, the minimal counterexample might not exist (e.g., in the real numbers), so the method is specific to well-ordered sets like ℕ.