Course contentsShow
← Mathematics
Lesson 2511 of 3,12150. Discrete Math — Logic and ProofFree lesson

When to Use Induction

Recognizing problem types where induction is the natural proof technique versus when other methods are more appropriate.

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.