Questions: Strong Induction and Well-Ordering Principle

Question 1

A proof that every integer n ≥ 2 has a prime factorization uses the inductive step: if n+1 = ab for 2 ≤ a, b < n+1, then a and b have factorizations (by hypothesis), giving one for n+1. Why does weak induction fail here while strong induction succeeds?

• A. Weak induction cannot handle claims about integers ≥ 2; it only works for integers ≥ 1
• B. Weak induction only provides P(k), but the proof needs P(a) and P(b) for a, b that may be much less than k
• C. Weak induction is a logically weaker theorem and can prove fewer statements than strong induction
• D. Strong induction is required whenever the base case is not n = 1

Answer: (B)

Weak induction gives you P(k) to prove P(k+1). In this proof, k+1 factors into a and b, both of which are less than k+1 but not necessarily equal to k. We need the prime factorization of a and b — both arbitrary values below k+1 — not just of k. Strong induction provides P(1) ∧ P(2) ∧ … ∧ P(k), covering all prior cases, which is exactly what's needed. Importantly, strong induction is not a 'stronger theorem' — it and weak induction are logically equivalent.

Question 2

A student decides to use strong induction for a problem because 'strong induction is more powerful and I want to be safe.' What is the conceptual error?

• A. Strong induction is harder to write and introduces unnecessary complexity
• B. Strong induction is only valid for proofs about prime numbers
• C. Strong induction and weak induction are logically equivalent — neither can prove anything the other cannot
• D. Using a stronger hypothesis makes the inductive step harder to establish

Answer: (C)

Strong induction, weak induction, and the well-ordering principle are all logically equivalent — they are three faces of the same axiom about natural numbers. No statement is provable by one but not the others. The word 'strong' refers to the stronger inductive hypothesis assumed, not to a more powerful proof system. Choosing strong induction should be motivated by proof structure (needing multiple prior cases), not by a desire for extra safety.

Question 3

Because it uses a stronger inductive hypothesis, strong induction can prove statements that are extremely difficult to prove using weak induction.

• T. True
• F. False

Answer: False

Strong induction and weak induction are logically equivalent — any theorem provable by one is provable by the other. Strong induction is sometimes more *convenient* when the proof of P(k+1) depends on multiple prior cases, but it isn't more *powerful*. The name 'strong' is potentially misleading: it refers to the hypothesis being assumed, not to the strength of conclusions that can be reached.

Question 4

The well-ordering principle — every non-empty set of positive integers has a smallest element — can be derived from mathematical induction, and induction can be derived from well-ordering. They are logically equivalent.

• T. True
• F. False

Answer: True

These are three faces of the same foundational axiom about ℕ: weak induction, strong induction, and the well-ordering principle are all mutually derivable. To see WOP → induction: if P(n) fails somewhere, the set of counterexamples has a smallest element m; the inductive step then gives P(m) from P(m-1), contradicting m being a counterexample. In practice, choose the form that fits your argument's structure most naturally.

Question 5

Why is strong induction sometimes more convenient than weak induction, even though they are logically equivalent?

Model answer: When the proof of P(k+1) requires P(j) for some j strictly less than k — not just P(k) — strong induction provides the needed hypothesis directly. Weak induction only gives P(k), which may have no direct relationship to k+1. The prime factorization example is canonical: proving k+1 factors into primes requires factoring its divisors a and b, which could be much smaller than k. Logical equivalence means the same theorem is ultimately provable either way; strong induction is just the form that matches the argument's natural structure.

A related use case: Fibonacci-type recurrences where F(n) = F(n-1) + F(n-2) require both F(k) and F(k-1) to prove F(k+1). Weak induction gives only F(k), missing the second needed term. Strong induction gives the entire range. The choice between the two forms should always be driven by what the inductive step naturally needs — not by preference for one form over the other.