Recurrence Relations

Definition

A recurrence relation defines a sequence where each term is expressed as a function of previous terms.

$a_n = f(a_{n-1}, a_{n-2}, \ldots, a_{n-k})$

with initial conditions specifying $a_0, a_1, \ldots, a_{k-1}$.

Famous Examples

Fibonacci Sequence

$F_n = F_{n-1} + F_{n-2}, \quad F_0 = 0, F_1 = 1$

Sequence: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$

Tower of Hanoi

$T_n = 2T_{n-1} + 1, \quad T_1 = 1$

Minimum moves to transfer $n$ disks: $T_n = 2^n - 1$

Factorial

$n! = n \cdot (n-1)!, \quad 0! = 1$

Linear Homogeneous Recurrences

Constant Coefficients

$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$

Characteristic Equation

Replace $a_n$ with $r^n$: $r^n = c_1 r^{n-1} + c_2 r^{n-2} + \cdots + c_k r^{n-k}$

Divide by $r^{n-k}$: $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0$

Solutions

Distinct roots $r_1, r_2, \ldots, r_k$: $a_n = \alpha_1 r_1^n + \alpha_2 r_2^n + \cdots + \alpha_k r_k^n$

Repeated root $r$ with multiplicity $m$: $(\alpha_1 + \alpha_2 n + \alpha_3 n^2 + \cdots + \alpha_m n^{m-1}) r^n$

Use initial conditions to solve for $\alpha$ values.

Second-Order Examples

Example 1: Fibonacci

$F_n = F_{n-1} + F_{n-2}$

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

Roots: $r = \frac{1 \pm \sqrt{5}}{2}$

Let $\phi = \frac{1 + \sqrt{5}}{2}$ (golden ratio) and $\hat{\phi} = \frac{1 - \sqrt{5}}{2}$

General solution: $F_n = \alpha_1 \phi^n + \alpha_2 \hat{\phi}^n$

Using $F_0 = 0, F_1 = 1$: $F_n = \frac{\phi^n - \hat{\phi}^n}{\sqrt{5}} = \frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right]$

Example 2: Repeated Roots

$a_n = 4a_{n-1} - 4a_{n-2}, \quad a_0 = 1, a_1 = 4$

Characteristic equation: $r^2 - 4r + 4 = 0$

Root: $r = 2$ (multiplicity 2)

General solution: $a_n = (\alpha_1 + \alpha_2 n) 2^n$

Using initial conditions:

• $a_0 = 1$: $\alpha_1 = 1$
• $a_1 = 4$: $(\alpha_1 + \alpha_2) \cdot 2 = 4 \Rightarrow \alpha_2 = 1$

Solution: $a_n = (1 + n) 2^n$

Non-Homogeneous Recurrences

Form: $a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + f(n)$

Method: Particular + Homogeneous

1. Find general solution to homogeneous part: $a_n^{(h)}$
2. Find one particular solution: $a_n^{(p)}$
3. General solution: $a_n = a_n^{(h)} + a_n^{(p)}$

Finding Particular Solutions

$f(n)$	Try
Constant $c$	$a_n^{(p)} = A$
Polynomial $n^d$	$a_n^{(p)} = A_d n^d + \cdots + A_0$
Exponential $s^n$	$a_n^{(p)} = A s^n$

If the trial solution is already part of the homogeneous solution, multiply by $n$.

Example

$a_n = 2a_{n-1} + 3^n, \quad a_0 = 1$

Homogeneous solution: $a_n^{(h)} = \alpha \cdot 2^n$

Particular solution: Try $a_n^{(p)} = A \cdot 3^n$

Substituting: $A \cdot 3^n = 2A \cdot 3^{n-1} + 3^n$ $A = \frac{2A}{3} + 1 \Rightarrow A = 3$

General solution: $a_n = \alpha \cdot 2^n + 3 \cdot 3^n$

Using $a_0 = 1$: $\alpha + 3 = 1 \Rightarrow \alpha = -2$

Solution: $a_n = -2 \cdot 2^n + 3^{n+1} = 3^{n+1} - 2^{n+1}$

Divide and Conquer Recurrences

Master Theorem

For $T(n) = aT(n/b) + f(n)$ where $a \geq 1$, $b > 1$:

Let $c = \log_b a$. Compare $f(n)$ to $n^c$:

1. If $f(n) = O(n^{c-\epsilon})$ for some $\epsilon > 0$: $T(n) = \Theta(n^c)$
2. If $f(n) = \Theta(n^c)$: $T(n) = \Theta(n^c \log n)$
3. If $f(n) = \Omega(n^{c+\epsilon})$ and regularity condition: $T(n) = \Theta(f(n))$

Common Examples

Recurrence	Solution
$T(n) = T(n/2) + O(1)$	$O(\log n)$ (binary search)
$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$ (merge sort)
$T(n) = 2T(n/2) + O(1)$	$O(n)$ (tree traversal)
$T(n) = T(n/2) + O(n)$	$O(n)$

Generating Functions

Define $G(x) = \sum_{n=0}^{\infty} a_n x^n$

Recurrence becomes an algebraic equation in $G(x)$.

Example: For $a_n = 2a_{n-1} + 1$, $a_0 = 0$:

$G(x) = 2xG(x) + \frac{1}{1-x}$ $G(x) = \frac{1}{(1-x)(1-2x)}$

Expand using partial fractions to find $a_n$.