A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Strong induction assumes all values from the base case up to k (not just P(k)) to prove P(k+1). This is logically equivalent to weak induction but sometimes more convenient. The well-ordering principle states that every non-empty set of positive integers has a smallest element; it is logically equivalent to induction. Strong induction is useful for recursive proofs.
Identify problems where assuming multiple previous cases simplifies the proof. Compare weak and strong induction on the same problem to see when strong induction helps.
From weak (standard) induction you know the template: prove a base case P(1), then prove that P(k) implies P(k+1), and conclude P(n) holds for all n ≥ 1. Strong induction modifies the inductive step: instead of assuming only P(k), you assume P(1) ∧ P(2) ∧ … ∧ P(k) — all cases up to k — and use this stronger hypothesis to prove P(k+1). The conclusion is identical: P(n) holds for all n ≥ 1. The name "strong" refers to the stronger inductive hypothesis, not a more powerful result.
Why would a stronger hypothesis help? Consider proving that every integer n ≥ 2 has a prime factorization. When proving P(k+1): if k+1 is prime, we're done. If not, k+1 = ab for some a, b with 2 ≤ a, b < k+1. By our inductive hypothesis (applied to *a* and *b*, not just *k*), both a and b have prime factorizations, and their product gives one for k+1. Weak induction would only give us P(k) — the factorization of k — which is useless here since k has no direct relationship to k+1. Strong induction is the natural tool whenever the proof of the next case depends on *some* previous case, not necessarily the immediately preceding one.
The well-ordering principle states that every non-empty subset S of the positive integers has a smallest element. This seems obvious but it is actually a foundational axiom for ℕ (or an equivalent one). Its connection to induction is tight: you can derive the well-ordering principle from induction and vice versa. To see the direction WOP → induction: suppose P(n) fails for some n. Then the set of counterexamples {n ∈ ℕ : ¬P(n)} is non-empty, so by WOP it has a smallest element m. Since P(1) holds (base case), m > 1, and m−1 satisfies P (since m was minimal). But then the inductive step gives P(m), a contradiction. Well-ordering is often used directly in proofs — particularly in descent arguments, where you assume a minimal counterexample exists and derive a smaller one, reaching a contradiction.
The logical equivalence of weak induction, strong induction, and well-ordering means none is "more powerful" — they are three faces of the same axiom about the natural numbers. Choose the form that most naturally fits the structure of your argument: strong induction when case k+1 depends on multiple prior cases, well-ordering when it's easiest to reason about a minimal counterexample, and weak induction when one step at a time suffices.