Recurrence Summary

Combinatorics · Axiom Academy

Let's review the key concepts from Unit 7 on recurrence relations and their solving methods. What Are Recurrence Relations? Definition: An equation that defines a sequence recursively, where each term is expressed in terms of previous terms Initial Conditions: Base values needed to uniquely determine the sequence (e.g., a₀ = 1, a₁ = 1 for Fibonacci) Order: The number of previous terms used in the relation (e.g., aₙ = aₙ₋₁ + aₙ₋₂ is second-order) Why It Matters: Models naturally recursive processes in computer science, biology, finance, and combinatorics Linear Homogeneous: Each term is a linear combination of previous terms with constant coefficients (e.g., aₙ = 3aₙ₋₁ - 2aₙ₋₂) Linear Non-Homogeneous: Includes an additional function of n (e.g., aₙ = 2aₙ₋₁ + n) Divide-and-Conquer: Breaks problems into smaller subproblems (e.g., T(n) = 2T(n/2) + n for mergesort) Special Sequences: Named sequences like Fibonacci, Catalan, and Stirling numbers Example Recap: Solving aₙ = 3aₙ₋₁ - 2aₙ₋₂ with a₀ = 1, a₁ = 2 Step 1 - Form Characteristic Equation: Replace aₙ with x², aₙ₋₁ with x, and aₙ₋₂ with 1 to get x² = 3x - 2 Step 2 - Solve for Roots: Rearrange to x² - 3x + 2 = 0, factor as (x - 1)(x - 2) = 0, giving roots r₁ = 1 and r₂ = 2 Step 3 - Write General Solution: aₙ = A₁(1)ⁿ + A₂(2)ⁿ = A₁ + A₂·2ⁿ Step 4 - Apply Initial Conditions: a₀ = 1 gives A₁ + A₂ = 1; a₁ = 2 gives A₁ + 2A₂ = 2 Step 5 - Solve System: Subtracting equations yields A₂ = 1, so A₁ = 0

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