6.2 Strong Induction and Well-Ordering

Strong Induction and Well-Ordering

Principles of Strong Induction

In ordinary (simple) induction, the inductive step assumes only that $P(n)$ is true and uses that to prove $P(n+1)$. Strong induction removes that restriction: you get to assume $P(j)$ is true for every value from the base case up through $n$, and then you prove $P(n+1)$.

The structure looks like this:

1. Base case: Show $P(1)$ is true (or whatever your starting value is).
2. Inductive step: Assume $P(1), P(2), \ldots, P(k)$ are all true. Using that assumption, prove $P(k+1)$.

Why bother? Because many statements about $P(n+1)$ depend on more than just the immediately preceding case. For example, the Fibonacci recurrence $F(n) = F(n-1) + F(n-2)$ reaches back two steps, so a proof about Fibonacci numbers naturally needs both $P(n-1)$ and $P(n)$. Strong induction hands you all previous cases at once, which often makes the argument shorter and more natural.

Despite the name, strong induction is logically equivalent to simple induction. Neither one can prove something the other can't. Strong induction just gives you a more convenient assumption to work with in certain proofs.

Well-Ordering Principle and Minimum Element

The Well-Ordering Principle says: every non-empty set of positive integers has a least (minimum) element.

This sounds obvious, but it's surprisingly powerful. It's one of the foundational properties of the natural numbers, closely tied to the Peano axioms, and it turns out to be logically equivalent to both simple and strong induction.

A key application is proof by contradiction. If you want to show some property holds for all positive integers, you can assume it fails somewhere, collect all the counterexamples into a set, and then invoke well-ordering to grab the smallest counterexample. Working with that smallest counterexample often produces a contradiction.

One thing to watch: the well-ordering principle applies to sets that have a well-ordering, meaning every non-empty subset has a least element. The positive integers and the non-negative integers are well-ordered under their usual ordering. The rational numbers under their usual ordering are not well-ordered (there's no smallest positive rational), so you can't blindly apply this principle to every number system.

Second Principle of Induction

This is just another name for strong induction (also called complete induction). The phrasing differs slightly from the version above but the idea is identical:

1. Base case: Show $P(1)$ is true.
2. Inductive step: For an arbitrary positive integer $k$, assume $P(m)$ is true for all $m < k$. Prove $P(k)$.

Notice the subtle difference in indexing compared to the earlier formulation: here you assume everything strictly less than $k$ and prove $P(k)$ itself, rather than assuming up through $k$ and proving $P(k+1)$. Both formulations are equivalent; different textbooks just prefer one or the other. Make sure you know which version your course uses so your proofs match the expected format.

Proof Techniques

Complete Induction Method

Here's a step-by-step template for writing a strong induction proof:

1. State the property. Write $P(n)$ clearly. For example: "Every integer $n \geq 2$ can be written as a product of primes."
2. Prove the base case. Verify $P$ for the smallest relevant value. (For the example: $2$ is itself prime, so it's a product of one prime.)
3. State the inductive hypothesis. Assume $P(j)$ holds for every integer $j$ with $2 \leq j \leq k$ (or $j < k$, depending on your formulation).
4. Prove the inductive step. Show $P(k+1)$ follows. This is where you get to use any of the assumed cases, not just $P(k)$. For the prime factorization example: if $k+1$ is prime, you're done; if not, $k+1 = ab$ where $2 \leq a, b \leq k$, and by the inductive hypothesis both $a$ and $b$ have prime factorizations, so $k+1$ does too.
5. Conclude. By strong induction, $P(n)$ is true for all integers $n \geq 2$.

Sometimes you need more than one base case. If your recurrence or argument reaches back $r$ steps, you typically need base cases for the first $r$ values. The Fibonacci example mentioned earlier would need both $P(1)$ and $P(2)$ verified.

Proof by Minimum Counterexample

This technique combines the Well-Ordering Principle with proof by contradiction. It's a clean alternative to induction for many of the same problems.

1. Assume the statement fails. Suppose there exists some positive integer for which $P(n)$ is false.
2. Form the set of counterexamples. Let $S = \{ n \in \mathbb{Z}^+ : P(n) \text{ is false} \}$. By your assumption, $S$ is non-empty.
3. Apply well-ordering. Since $S$ is a non-empty set of positive integers, it has a least element. Call it $n_0$.
4. Derive a contradiction. Use the fact that $n_0$ is the smallest counterexample. This means $P(j)$ is true for every positive integer $j < n_0$. Exploit that to show $P(n_0)$ must actually be true as well, contradicting the assumption that $n_0 \in S$.
5. Conclude. The set $S$ must be empty, so $P(n)$ holds for all positive integers.

This method is especially common in number theory. For instance, proving that every integer $\geq 2$ has a prime divisor works neatly by minimum counterexample: the smallest integer $\geq 2$ that lacks a prime divisor would itself have to be prime (contradiction) or factor into smaller pieces that do have prime divisors (also a contradiction).

Comparison with Other Methods

Advantages and Limitations of Strong Induction

When strong induction helps most:

• The inductive step naturally depends on multiple earlier cases, not just the immediate predecessor. Recursive definitions (like Fibonacci) and divisibility arguments are classic examples.
• You want a cleaner proof structure. Some proofs that can be done with simple induction require an awkward strengthening of the hypothesis; strong induction avoids that.
• You're proving correctness of a recursive algorithm whose recursive calls don't just reduce the input by one.

Things to watch out for:

• Base cases. Because the inductive step can reach back to any earlier case, you may need to verify several base cases, not just one. Missing a base case is a common mistake.
• Circular reasoning. Make sure your argument for $P(k+1)$ genuinely uses the assumption on smaller values. If you accidentally assume $P(k+1)$ itself, the proof is circular.
• Choosing the right method. Strong induction, simple induction, and minimum counterexample are all logically equivalent for statements about positive integers. Pick whichever makes the argument clearest. There's no bonus for using a fancier technique when simple induction works fine.