Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 68 ยท Proof Techniques

Strong Induction and Well-Ordering

Learn strong induction, the well-ordering principle and structural induction on lists and trees, with prime factorization and stamp examples in Python.

Ordinary induction leans on one domino: to prove P(k+1) you may use P(k). But many facts about integers need more than the previous case. When you split a number into two smaller factors, those factors can be anywhere below it, not just one step down. For that, you need an induction that may use all earlier cases.

This lesson introduces strong induction, its close cousin the well-ordering principle, and structural induction, which proves facts about lists and trees by following how they are built. All three are really the same idea as recursion, and they are what you reach for when proving the correctness of recursive algorithms.

Strong induction

To prove P(n) for all n โ‰ฅ nโ‚€ by strong induction:

  1. Base case(s). Prove P(nโ‚€) (sometimes several starting values).
  2. Inductive step. Let k โ‰ฅ nโ‚€. Assume P(m) for every m with nโ‚€ โ‰ค m โ‰ค k and prove P(k+1).

Strong induction is not more powerful than ordinary induction: anything provable with one is provable with the other (apply ordinary induction to the statement "P(m) holds for all m โ‰ค n"). It is simply more convenient when the step needs several earlier cases.

Ordinary vs strong induction

Ordinary Assume only P(k) to prove P(k+1).
Strong Assume P(m) for every m up to k.
Same power Each can simulate the other.

Use strong induction when the recursive pieces are not just one step smaller.

1 / 2

Every integer above 1 is a product of primes

Theorem. Every integer n โ‰ฅ 2 is a prime or a product of primes.

Proof (strong induction). Let P(n) be the statement. Base case: 2 is prime. Step: let k โ‰ฅ 2 and assume P(m) for all m with 2 โ‰ค m โ‰ค k. Consider k + 1. If it is prime, we are done. Otherwise k + 1 = a ร— b with 2 โ‰ค a, b โ‰ค k. By the hypothesis, both a and b are primes or products of primes, so their product is a product of primes. โˆŽ

Ordinary induction fails here, because knowing only that k is a product of primes says nothing about the factors a and b of k + 1. The proof is also an algorithm: it is exactly how a recursive factorization function works.

Python The proof as a recursive function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The recursion lines up with the proof. The base case is "no divisor means prime". The recursive call is on d and n // d, which are both smaller than n but not necessarily n - 1.

Stamps: strong induction with several base cases

Theorem. Every postage amount of 12 cents or more can be made with 4-cent and 5-cent stamps.

Proof. Base cases: 12 = 4+4+4, 13 = 4+4+5, 14 = 4+5+5, 15 = 5+5+5. Step: let k โ‰ฅ 15 and assume every amount from 12 to k can be made. Then k + 1 โ‰ฅ 16, so k + 1 - 4 โ‰ฅ 12 and is at most k. By the hypothesis, k + 1 - 4 can be made. Add one 4-cent stamp. โˆŽ

The step reaches back four values, so we need four base cases. That is the typical reason for several base cases: the number of base cases matches how far back the step reaches.

Python Build every amount from earlier amounts

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line lists the amounts below 12 that cannot be made: 1, 2, 3, 6, 7 and 11. This is why the theorem starts at 12.

The well-ordering principle

The well-ordering principle says: every non-empty set of non-negative integers has a smallest element. It sounds obvious, but it is an equivalent form of induction, and a powerful proof tool. A proof using it often runs: suppose the claim fails somewhere; then there is a smallest counterexample; derive a smaller counterexample; contradiction.

Theorem. Every integer n โ‰ฅ 2 has a prime divisor.

Proof. Suppose not. Then the set of integers n โ‰ฅ 2 with no prime divisor is non-empty, so it has a smallest member n. That n is not prime (a prime divides itself), so n = a ร— b with 2 โ‰ค a < n. Then a is smaller than n, so a has a prime divisor, and that prime divides n too. Contradiction. โˆŽ

Note that this is a contradiction proof (see Contradiction and Contrapositive) built on the least element. The principle fails on the non-negative rationals or reals (the set of positive reals has no smallest member), which is why induction is specifically a statement about integers.

The "smallest counterexample" idea is also a debugging strategy: when a test fails on a big input, shrink it to the smallest failing input. Tools for property-based testing do that automatically.

Python Searching for the smallest counterexample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Structural induction

Many objects are defined recursively: a list is empty or an element followed by a list; a binary tree is empty or a root with two subtrees; a formula is a variable or built from smaller formulas with AND, OR, NOT. Structural induction proves a property of every such object in two steps:

  1. Base case. The property holds for the simplest objects (the empty list, a single leaf).
  2. Constructor step. If the property holds for the smaller pieces used in a constructor, it holds for the object built from them.

It is ordinary induction on the number of times the constructors were used, written in a more natural way.

Theorem. In a full binary tree (every node has 0 or 2 children), the number of leaves is one more than the number of internal nodes.

Proof. A single leaf has 1 leaf and 0 internal nodes. Now build a tree from a root and two full subtrees with Lโ‚, Iโ‚ and Lโ‚‚, Iโ‚‚ leaves and internal nodes. By hypothesis Lโ‚ = Iโ‚ + 1 and Lโ‚‚ = Iโ‚‚ + 1. The new tree has Lโ‚ + Lโ‚‚ leaves and Iโ‚ + Iโ‚‚ + 1 internal nodes, and Lโ‚ + Lโ‚‚ = Iโ‚ + Iโ‚‚ + 2 = (Iโ‚ + Iโ‚‚ + 1) + 1. โˆŽ

Python Structural induction on trees and lists

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The functions leaves and internal mirror the proof: one clause for the base object and one for the constructor. That match between recursive definitions and inductive proofs is not a coincidence.

Unique factorization and recursion

The theorem proved earlier says a factorization into primes exists. The Fundamental Theorem of Arithmetic adds that it is unique apart from order. Uniqueness uses a lemma of Euclid: if a prime p divides a ร— b, then p divides a or b. The usual proof of uniqueness takes a smallest number with two different factorizations (well-ordering) and cancels a shared prime to get a smaller counterexample. You will use the theorem constantly in Divisibility and Primes.

Throughout this lesson, the pattern has been the same: a recursive definition, a recursive algorithm, and an inductive proof are three views of one idea. When you write a recursive function, ask the proof questions: does every call reach a base case, and does each call trust the result for smaller inputs? Answering yes is a proof by (strong or structural) induction that the function works.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does strong induction let you assume when proving P(k+1)?

    Strong induction assumes the statement for every earlier value, not just the immediately previous one. Assuming P(k+1) or later values would be circular.
  2. 2. In the stamp proof, why are four base cases (12 to 15) needed?

    The step builds k+1 from k+1-4, so the step only works once k+1-4 is already known to be possible (at least 12). The amounts 12, 13, 14 and 15 have no such predecessor and must be checked directly.
  3. 3. Which statement is the well-ordering principle?

    Well-ordering says non-empty sets of non-negative integers have a least member. It fails for the positive reals, which have no smallest element.
  4. 4. A full binary tree has 7 internal nodes. How many leaves does it have?

    By structural induction, leaves = internal nodes + 1, so there are 8.

Summary

  • Strong induction assumes P(m) for all earlier m and proves P(k+1); it is equivalent in power to ordinary induction but more convenient for factoring-like steps.
  • The number of base cases equals how far back the step reaches (stamps: 12 to 15).
  • Well-ordering says non-empty sets of non-negative integers have a least element; "smallest counterexample" proofs rely on it.
  • Structural induction proves properties of recursively defined objects (lists, trees, formulas) by checking base objects and constructors.
  • Recursive definitions, recursive code and inductive proofs are three views of the same idea.
  • Prime factorization exists by strong induction; uniqueness is the Fundamental Theorem of Arithmetic.

Next: Divisibility and Primes.