Recurrence Relations

A recurrence relation defines a sequence where each term is a function of preceding terms. They are the discrete analogues of differential equations.

Classification

Linear: Terms appear to the first power.
Homogeneous: No constant terms or separate functions of $n$ .
Order: The number of previous terms required.

Solving Linear Homogeneous Recurrences

For $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ , we solve the Characteristic Equation: $r^2 - c_1 r - c_2 = 0$

Interactive Lab

import numpy as np

def solve_recurrence(c1, c2, a0, a1, n):
  # Solves a_n = c1*a_{n-1} + c2*a_{n-2}
  roots = np.roots([1, -c1, -c2])
  r1, r2 = roots
  
  # a_n = A*r1^n + B*r2^n
  # a0 = A + B
  # a1 = A*r1 + B*r2
  A_mat = np.array([[1, 1], [r1, r2]])
  B_vec = np.array([a0, a1])
  A, B = np.linalg.solve(A_mat, B_vec)
  
  return A * (r1**n) + B * (r2**n)

# Fibonacci example: a_n = 1*a_{n-1} + 1*a_{n-2}, a0=0, a1=1
val = solve_recurrence(1, 1, 0, 1, 10)
print(f"F(10) via Characteristic Equation: {round(val.real)}")

python

1import numpy as np

3def solve_recurrence(c1, c2, a0, a1, n):

4 # Solves a_n = c1*a_{n-1} + c2*a_{n-2}

5 roots = np.roots([1, -c1, -c2])

6 r1, r2 = roots

8 # a_n = A*r1^n + B*r2^n

9 # a0 = A + B

10 # a1 = A*r1 + B*r2

11 A_mat = np.array([[1, 1], [r1, r2]])

12 B_vec = np.array([a0, a1])

13 A, B = np.linalg.solve(A_mat, B_vec)

15 return A * (r1**n) + B * (r2**n)

17# Fibonacci example: a_n = 1*a_{n-1} + 1*a_{n-2}, a0=0, a1=1

18val = solve_recurrence(1, 1, 0, 1, 10)

19print(f"F(10) via Characteristic Equation: {round(val.real)}")

Binet’s Formula for Fibonacci

The closed-form solution for Fibonacci is: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}, \quad \phi = \frac{1+\sqrt{5}}{2}$

Interactive Lab

def binet_fib(n):
  phi = (1 + 5**0.5) / 2
  psi = (1 - 5**0.5) / 2
  return round((phi**n - psi**n) / 5**0.5)

print(f"F(20) via Binet: {binet_fib(20)}")

python

1def binet_fib(n):

2 phi = (1 + 5**0.5) / 2

3 psi = (1 - 5**0.5) / 2

4 return round((phi**n - psi**n) / 5**0.5)

6print(f"F(20) via Binet: {binet_fib(20)}")

Divide and Conquer: The Master Theorem

In CS, we often see $T(n) = aT(n/b) + f(n)$ .

Merge Sort: $T(n) = 2T(n/2) + n \implies O(n \log n)$ .
Binary Search: $T(n) = T(n/2) + 1 \implies O(\log n)$ .

What is the characteristic equation for the recurrence $a_n = 5a_{n-1} - 6a_{n-2}$?

Computational Methods: Matrix Exponentiation

For terms like $F_{10^9}$ , floating point precision fails. We use the transformation matrix $M$ where $M^n$ gives the $n$ -th term in $O(\log n)$ time.

Interactive Lab

def matrix_mult(A, B):
  C = [[0, 0], [0, 0]]
  for i in range(2):
      for j in range(2):
          for k in range(2):
              C[i][j] += A[i][k] * B[k][j]
  return C

def matrix_pow(A, p):
  res = [[1, 0], [0, 1]]
  while p > 0:
      if p % 2 == 1: res = matrix_mult(res, A)
      A = matrix_mult(A, A)
      p //= 2
  return res

T = [[1, 1], [1, 0]]
T_n = matrix_pow(T, 10)
print(f"F(10) via Matrix Exponentiation: {T_n[0][1]}")

python

1def matrix_mult(A, B):

2 C = [[0, 0], [0, 0]]

3 for i in range(2):

4 for j in range(2):

5 for k in range(2):

6 C[i][j] += A[i][k] * B[k][j]

7 return C

9def matrix_pow(A, p):

10 res = [[1, 0], [0, 1]]

11 while p > 0:

12 if p % 2 == 1: res = matrix_mult(res, A)

13 A = matrix_mult(A, A)

14 p //= 2

15 return res

17T = [[1, 1], [1, 0]]

18T_n = matrix_pow(T, 10)

19print(f"F(10) via Matrix Exponentiation: {T_n[0][1]}")

Recurrence Relations

Recurrence Relations

Classification

Solving Linear Homogeneous Recurrences

Binet’s Formula for Fibonacci

Divide and Conquer: The Master Theorem

What is the characteristic equation for the recurrence $a_n = 5a_{n-1} - 6a_{n-2}$?

Computational Methods: Matrix Exponentiation

Which growth rate does Merge Sort follow based on its recurrence relation T(n) = 2T(n/2) + n?