Induction on Recursively Defined Sequences
What You'll Learn
You'll learn how to use mathematical induction to prove properties of sequences that are defined by recurrence relations, leveraging their recursive structure.
The Core Idea
Many sequences in mathematics aren't given by explicit formulas like aₙ = 3n + 2, but instead by recurrence relations that define each term using previous terms. For example:
aₙ = 2aₙ₋₁ + 1witha₁ = 1- The Fibonacci sequence:
Fₙ = Fₙ₋₁ + Fₙ₋₂withF₁ = F₂ = 1
When proving properties about such sequences, induction is the natural tool because the sequence itself is built inductively.
The Strategy
The recursive definition gives you exactly what you need for the inductive step:
- Base case: Verify the property holds for the initial term(s) given in the definition
- Inductive hypothesis: Assume the property holds for all terms up to
aₖ(or justaₖ, depending on the recurrence) - Inductive step: Use the recurrence relation to express
aₖ₊₁in terms of previous terms, then apply your hypothesis to prove the property foraₖ₊₁
The recursive structure provides a built-in connection between consecutive terms—you're just making that connection explicit in your proof.
Example Pattern
To prove that aₙ = 3·2ⁿ - 2 when aₙ = 2aₙ₋₁ + 2 and a₁ = 4:
- Base:
a₁ = 4 = 3·2¹ - 2 ✓ - Inductive step: Assume
aₖ = 3·2ᵏ - 2. Then by the recurrence:aₖ₊₁ = 2aₖ + 2 = 2(3·2ᵏ - 2) + 2 = 3·2ᵏ⁺¹ - 4 + 2 = 3·2ᵏ⁺¹ - 2 ✓
Key Takeaway: When proving properties of recursively defined sequences, use induction with the recurrence relation itself as your bridge from aₖ to aₖ₊₁—the recursive structure and inductive structure are perfect partners.