Recurrence Relations

Recurrence Relations

---

Definitions

---

Formulas

---

Solving Linear Homogeneous Recurrences

Step-by-Step Method

1. Write the characteristic equation from the recurrence
2. Solve the characteristic equation for roots $r_1, r_2, \ldots$
3. If roots are distinct: $a_n = A_1 r_1^n + A_2 r_2^n + \cdots$
4. If a root $r$ has multiplicity $m$: include terms $(A_1 + A_2 n + \cdots + A_m n^{m-1}) r^n$
5. Use initial conditions to solve for constants $A_i$

Example: Fibonacci Sequence

The Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0, F_1 = 1$:

Characteristic equation: $r^2 - r - 1 = 0$

Roots: $r_1 = \phi = \frac{1+\sqrt{5}}{2} \approx 1.618$, $r_2 = \psi = \frac{1-\sqrt{5}}{2} \approx -0.618$

General solution: $F_n = A \phi^n + B \psi^n$

Using initial conditions: $A = \frac{1}{\sqrt{5}}$, $B = -\frac{1}{\sqrt{5}}$

Closed form: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$

---

Python Implementations

Solving Linear Recurrences

import numpy as np
from functools import lru_cache

def solve_linear_recurrence(c1, c2, a0, a1, n):
    """Solve a_n = c1*a_{n-1} + c2*a_{n-2}."""
    coeffs = [1, -c1, -c2]
    roots = np.roots(coeffs)

    if len(set(np.round(roots, 10))) == 2:
        r1, r2 = roots
        A = (a1 - r2 * a0) / (r1 - r2)
        B = a0 - A
        return A * r1**n + B * r2**n
    else:
        r = roots[0]
        return (a0 + n * (a1 / r - a0)) * r**n

# Fibonacci
for i in range(11):
    print(f"F({i}) = {solve_linear_recurrence(1, 1, 0, 1, i):.0f}")

Iterative Solution

def linear_recurrence_iterative(c1, c2, a0, a1, n):
    """Compute a_n iteratively."""
    if n == 0:
        return a0
    if n == 1:
        return a1
    prev2, prev1 = a0, a1
    for _ in range(2, n + 1):
        curr = c1 * prev1 + c2 * prev2
        prev2, prev1 = prev1, curr
    return prev1

# Verify
for n in range(11):
    print(f"F({n}) = {linear_recurrence_iterative(1, 1, 0, 1, n)}")

Memoized Recursion

@lru_cache(maxsize=None)
def fibonacci_memo(n):
    if n <= 1:
        return n
    return fibonacci_memo(n - 1) + fibonacci_memo(n - 2)

for i in range(20):
    print(f"F({i}) = {fibonacci_memo(i)}", end="  ")

---

Master Theorem

Master Theorem Applications

import math

def master_theorem(a, b, d):
    log_b_a = math.log(a) / math.log(b)
    if d < log_b_a:
        return f"O(n^{log_b_a:.2f})"
    elif abs(d - log_b_a) < 1e-9:
        return f"O(n^{d} log n)"
    else:
        return f"O(n^{d})"

print(master_theorem(2, 2, 1))  # O(n^1.00 log n) - Merge Sort
print(master_theorem(1, 2, 0))  # O(n^0.00 log n) = O(log n) - Binary Search
print(master_theorem(7, 2, 2))  # O(n^2.81) - Strassen

---

Non-Homogeneous Recurrences

---

Applications in AI/ML

---

Common Mistakes

---

Interview Questions

1. What is the Master theorem and when does it apply? It solves $T(n) = aT(n/b) + O(n^d)$ in three cases based on comparing $d$ with $\log_b a$. It applies only to divide-and-conquer recurrences.

2. How do you solve the Fibonacci recurrence? Characteristic equation $r^2 - r - 1 = 0$ gives roots $\phi$ and $\psi$. Closed form: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$.

3. What is the time complexity of merge sort and why? $O(n \log n)$. The recurrence $T(n) = 2T(n/2) + n$ satisfies Case 2 of Master theorem with $a=2, b=2, d=1$.

4. How do you solve a recurrence with repeated roots? If root $r$ has multiplicity 2, the solution is $(A + Bn)r^n$ instead of just $Ar^n$.

5. What is the difference between linear and non-linear recurrences? Linear recurrences express $a_n$ as a linear combination of previous terms. Non-linear recurrences involve products, powers, or other non-linear functions of previous terms.

6. How do you analyze recursive algorithms without Master theorem? Use the recursion tree method: sum work at each level, or use substitution method (guess and verify by induction).

7. What is the Akra-Bazzi method? Generalizes Master theorem for recurrences like $T(n) = aT(n/b) + f(n)$ where $f(n)$ can be any polynomial.

8. When does the Master theorem not apply? When the recurrence is not divide-and-conquer (e.g., $T(n) = T(n-1) + 1$), or when subproblems have unequal sizes.

---

Practice Problems

---

Recursion Tree Method

def recursion_tree_depth(T_func, n, depth=0):
    """Visualize recursion tree depth."""
    if n <= 1:
        return depth
    return T_func(n, depth)

def sum_of_geometric_series(a, r, n):
    """Sum of geometric series: a + ar + ar^2 + ... + ar^(n-1)."""
    if abs(r) < 1:
        return a * (1 - r**n) / (1 - r)
    return a * (r**n - 1) / (r - 1)

# Example: T(n) = 2T(n/2) + n has log2(n) levels, each doing n work
import math
for n in [8, 16, 32, 64]:
    levels = int(math.log2(n))
    total = sum(n // (2**i) * 2**i for i in range(levels + 1))
    print(f"T({n}): {levels} levels, total work ~ {total}, O(n log n) = {n * levels}")

---

Substitution Method

def substitution_verify(c1, c2, bound_func, n_values):
    """Verify a guessed bound satisfies the recurrence."""
    for n in n_values:
        if n <= 1:
            continue
        lhs = c1 * bound_func(n)
        rhs = c2 * bound_func(n // 2) + n
        if lhs < rhs:
            return False, n
    return True, None

import math
result, failing_n = substitution_verify(1, 2, lambda n: n * math.log2(n), [4, 8, 16, 32])
print(f"Bound O(n log n) verified: {result}")

---

Quick Reference

---

Cross-References

• Graph Theory — Discrete Graphs: BFS/DFS traversals have recursive definitions
• Trees — Discrete Trees: Tree height and operations satisfy recurrences
• Number Theory — Discrete Number Theory: Modular exponentiation uses recurrences
• Boolean Algebra — Discrete Boolean: Boolean function complexity
• Automata Theory — Discrete Automata: Grammar production rules are recursive
• Applications — Discrete Applications: Algorithm analysis uses recurrences extensively