When to Use Induction
You'll learn to recognize which problems naturally call for inductive reasoning versus other proof techniques.
Mathematical induction is powerful, but it's not a universal tool. Knowing when to reach for it—versus direct proof, contrapositive, or contradiction—makes you a more efficient problem-solver.
Induction Is Your Go-To When...
The problem involves all natural numbers (or integers beyond some starting point). If you see "for all n ≥ 1" or "for every positive integer n," induction should be on your radar.
The statement has a recursive or cumulative structure. Summation formulas (Σ), products (Π), divisibility claims, and sequences defined recursively all build from smaller cases—exactly what induction exploits. Think: "If I know it works for n, can I show it works for n+1 using the n-case?"
Direct methods get messy or circular. Sometimes algebraic manipulation leads nowhere. Induction lets you assume the k-case is true and leverage that assumption constructively.
When Induction Is Not the Best Choice
The statement doesn't involve "for all n." A claim like "√2 is irrational" or "there are infinitely many primes" doesn't index over natural numbers—contradiction or direct methods work better.
The property isn't cumulative. If knowing the result for k doesn't help you prove it for k+1, induction won't connect the dots.
A direct proof is simpler. For example, proving "n² - n is even" is easier by factoring n(n-1) and noting one factor is even—no induction needed.
The Analogy
Think of induction as climbing a ladder: you prove you can reach the first rung (base case) and that each rung leads to the next (inductive step). If the problem doesn't look like a ladder—if there's no sequential "next step"—you need a different tool.
Key Takeaway: Use induction for statements indexed by natural numbers with recursive or cumulative structure; otherwise, consider direct proof, contrapositive, or contradiction first.