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

Strong Induction for Sequences and Recurrences

Use strong induction to prove properties of recursively defined sequences.

Strong Induction for Sequences and Recurrences

What you'll learn: How to use strong induction to prove properties of recursively defined sequences where each term depends on multiple previous terms.

Why Strong Induction?

When a sequence is defined recursively—where each term depends on one or more earlier terms—ordinary induction often falls short. If computing a(n) requires knowing a(n-1) and a(n-2), your inductive step needs access to both previous values. Strong induction lets you assume the property holds for all previous cases, not just the immediate predecessor.

The Core Idea

For a recursively defined sequence like the Fibonacci numbers F(n) = F(n-1) + F(n-2), suppose you want to prove a formula or inequality about F(n).

Strong induction structure:

  1. Base case(s): Verify the property for the initial terms (often two or more)
  2. Inductive hypothesis: Assume the property holds for all k ≤ n (where n ≥ your base cases)
  3. Inductive step: Use the recurrence relation and the hypothesis to prove it holds for n+1

Why It Works

The recurrence relation expresses a(n+1) in terms of previous values. Since you've assumed those previous cases are true, you can substitute them directly into the recurrence to establish the next case.

Example analogy: Climbing a ladder where each rung might be supported by the previous two rungs—you need to know both lower rungs are stable before trusting the next one.

Common Applications

  • Proving closed-form formulas for recursive sequences
  • Establishing bounds or inequalities on growth rates
  • Showing divisibility properties that propagate through the recurrence

Key Takeaway: Strong induction is the natural tool for recursively defined sequences—assume all previous cases hold, then use the recurrence relation to prove the next step.