Recurrences Summary

Discrete Math · Axiom Academy

Let's review how recurrence relations model sequences, reveal algorithm complexity, and bridge discrete and continuous mathematics. What is a Recurrence Relation? Definition: An equation that defines each term of a sequence as a function of preceding terms, along with initial conditions Components: Recurrence equation + initial values uniquely determine the entire sequence Key Insight: Describes how to compute future values from past values, making them ideal for modeling iterative processes Connection: Discrete analog of differential equations—difference equations reveal behavior over steps rather than continuous time Linear: Each term is a linear combination of previous terms. Example: aₙ = c₁aₙ₋₁ + c₂aₙ₋₂ Homogeneous: No additional terms; only depends on previous sequence values. Example: F(n) = F(n-1) + F(n-2) Constant Coefficients: The multipliers c₁, c₂, ... don't depend on n Order: The number of previous terms needed. Fibonacci is order 2; Tower of Hanoi is order 1 Key Technique: Transform linear homogeneous recurrence into algebraic equation by assuming solution aₙ = rⁿ Process: Substitute rⁿ into recurrence, divide by rⁿ⁻ᵏ , obtain polynomial in r General Solution: Combine characteristic roots with coefficients determined by initial conditions Special Cases: Repeated roots require nrⁿ terms; complex roots yield trigonometric solutions Form: aₙ = c₁aₙ₋₁ + ... + cₖaₙ₋ₖ + f(n) where f(n) is the forcing function

This is the written version of the interactive lesson above. See the full Discrete Math course.