Recurrence Relations

Counting with Recurrences

A recurrence relation defines a sequence by expressing $a_n$ in terms of previous terms. Combined with initial conditions, it uniquely determines the sequence.

Linear Recurrences

A linear homogeneous recurrence with constant coefficients: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$

Characteristic equation: substitute $a_n = r^n$ to get $r^k = c_1 r^{k-1} + \cdots + c_k$. If roots $r_1, r_2, \ldots$ are distinct, the solution is: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots$

Fibonacci: $F_n = F_{n-1} + F_{n-2}$, $F_0=0$, $F_1=1$. Characteristic roots $r = \frac{1 \pm \sqrt{5}}{2}$ (golden ratio $\phi$ and its conjugate).

Towers of Hanoi

$T(n) = 2T(n-1) + 1$, $T(1)=1$. Closed form: $T(n) = 2^n - 1$.

def solve_linear_recurrence(coeffs, initial, n):
    seq = list(initial)
    k = len(coeffs)
    while len(seq) <= n:
        next_val = sum(coeffs[i] * seq[-(i+1)] for i in range(k))
        seq.append(next_val)
    return seq[n]

# Fibonacci: coeffs=[1,1], initial=[0,1]
print(solve_linear_recurrence([1, 1], [0, 1], 10))  # 55

Your Task

Implement solve_fibonacci, solve_linear_recurrence, and towers_of_hanoi_count.