mathbase

Reading

Core explanation

Recurrence relations define sequences in terms of earlier terms. Induction is a natural tool to prove closed forms or properties of such sequences.

Example: Let a₁ = 1, a₂ = 1, and aₙ = aₙ₋₁ + aₙ₋₂ (Fibonacci sequence). Suppose we want to prove a property like:

aₙ ≤ 2ⁿ for all n ≥ 1.

We might use strong induction:

Base cases: Check n = 1 and n = 2.
Induction Step: Assume the statement holds for all k ≤ n. Then: aₙ₊₁ = aₙ + aₙ₋₁ ≤ 2ⁿ + 2ⁿ⁻¹ = 2ⁿ⁻¹(2 + 1) = 3·2ⁿ⁻¹ < 2ⁿ⁺¹.

In many recurrence proofs:

You assume the property holds for several previous indices.
You combine these assumptions to show it holds for the next index.
Strong induction is more natural than weak induction.

TL;DR — key idea

Recurrence relation proofs usually pair a guessed formula with induction, often using strong induction when the next term depends on multiple previous ones.

Try these in your notebook

Don’t skip this – writing proofs or explanations on paper is where most of the learning actually happens.

1
Consider the sequence defined by: - a₁ = 2 - aₙ₊₁ = 3aₙ for n ≥ 1. Conjecture: aₙ = 2·3ⁿ⁻¹ for all n ≥ 1. Use induction to prove this formula. (Then think about how you might handle a more complicated recurrence with strong induction.)

Once you’ve sketched some ideas, summarize the main insight in the reflection box on the right.

Induction for Recurrence Relations

Reading

Try these in your notebook

Check your understanding