Choosing the Right Proof Technique
You'll learn how to select ordinary induction, strong induction, or well-ordering based on the structure of the problem you're trying to prove.
Now that you've mastered three powerful proof techniques for statements about natural numbers, the key question becomes: which one should you use? While these methods are logically equivalent, choosing the right tool makes your proof cleaner and more natural.
Recognizing Problem Structure
Use Ordinary Induction when:
- The statement at step
ndepends only on stepn-1 - You can build the next case directly from the previous one
- Example: proving sum formulas like
1 + 2 + ... + n = n(n+1)/2 - Analogy: Climbing a ladder one rung at a time—you only need the rung directly below you
Use Strong Induction when:
- The statement at step
nmight depend on multiple earlier cases - Recursive definitions involve looking back more than one step
- Example: proving properties of the Fibonacci sequence
F(n) = F(n-1) + F(n-2) - Analogy: Building a brick wall where each brick might rest on several bricks below, not just the one directly beneath
Use Well-Ordering when:
- You need to find a minimal counterexample
- The proof involves "smallest" or "least" elements
- Contradiction arguments feel most natural
- Example: proving every integer > 1 has a prime factorization
- Analogy: Finding the weakest link in a chain—if something fails, there must be a first failure point
Strategic Hints
If you're stuck, try strong induction—it's the most flexible since assuming more gives you more to work with. If the problem mentions "smallest" or "least," consider well-ordering.
Key Takeaway: Choose ordinary induction for sequential dependencies, strong induction for multi-step dependencies or recursive structures, and well-ordering when minimality or finding a smallest element drives the argument.