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

Induction on Recursively Defined Sequences

Proving properties of sequences defined by recurrence relations using their recursive structure.

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ₙ₋₁ + 1 with a₁ = 1
  • The Fibonacci sequence: Fₙ = Fₙ₋₁ + Fₙ₋₂ with F₁ = 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:

  1. Base case: Verify the property holds for the initial term(s) given in the definition
  2. Inductive hypothesis: Assume the property holds for all terms up to aₖ (or just aₖ, depending on the recurrence)
  3. Inductive step: Use the recurrence relation to express aₖ₊₁ in terms of previous terms, then apply your hypothesis to prove the property for aₖ₊₁

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.