Solving Linear Recurrence Relations

Solve recurrence relations using the characteristic equation method and verify with Python.

25 min read
Intermediate

Introduction

Many sequences are defined recursively - each term depends on previous terms. The Fibonacci sequence is a classic example. We'll learn to solve these recurrences systematically.

Learning Objectives:

  • Solve linear recurrence relations
  • Use the characteristic equation method
  • Verify solutions with Python

Linear Recurrence Relations

A linear recurrence with constant coefficients:

an=c1anโˆ’1+c2anโˆ’2+โ‹ฏ+ckanโˆ’ka_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}

with initial conditions a0,a1,...,akโˆ’1a_0, a_1, ..., a_{k-1}.

Example: Fibonacci Sequence

Fn=Fnโˆ’1+Fnโˆ’2,F0=0,F1=1F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1

Characteristic equation: Assume Fn=rnF_n = r^n:

rn=rnโˆ’1+rnโˆ’2r^n = r^{n-1} + r^{n-2} r2=r+1r^2 = r + 1 r2โˆ’rโˆ’1=0r^2 - r - 1 = 0

Roots: r=1ยฑ52r = \frac{1 \pm \sqrt{5}}{2} (golden ratio ฯ•\phi and ฯ•^\hat{\phi})

General solution:

Fn=Aฯ•n+Bฯ•^nF_n = A\phi^n + B\hat{\phi}^n

Using initial conditions: Fn=ฯ•nโˆ’ฯ•^n5F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}} (Binet's formula)

python
import math

def fibonacci_recursive(n):
    """Compute Fibonacci using recurrence"""
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

def fibonacci_closed_form(n):
    """Binet's formula"""
    phi = (1 + math.sqrt(5)) / 2
    psi = (1 - math.sqrt(5)) / 2
    return int((phi**n - psi**n) / math.sqrt(5))

print("Fibonacci sequence:")
print("\nRecursive vs Closed Form:")
for n in range(15):
    rec = fibonacci_recursive(n)
    closed = fibonacci_closed_form(n)
    print(f"  F_{n:<2} = {rec:>4} (closed form: {closed:>4}) โœ“" if rec == closed else f"  F_{n} mismatch!")

Key Takeaways

  1. Recurrence: Define sequence recursively
  2. Characteristic equation: Solve for roots
  3. General solution: Linear combination of roots
  4. Initial conditions: Determine constants
  5. Closed form: Direct formula for ana_n

Next Lesson: Combinatorial proofs and bijections!

๐ŸŽฒ

Combinatorics and Probability: From Counting to Inference

Master the mathematical foundations of counting, probability, and randomness. This comprehensive course bridges pure combinatorics with computational probability, covering everything from basic counting principles to advanced probabilistic methods, limit theorems, and real-world applications in algorithms, finance, and data science.