Recurrence Relations

A recurrence relation defines a sequence $\{a_n\}$ by expressing $a_n$ in terms of previous terms.

Example. Fibonacci: $F_n = F_{n-1} + F_{n-2}$With $F_0 = 0$, $F_1 = 1$.

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

Solution method. Form the characteristic equation:

$r^k + c_1 r^{k-1} + \cdots + c_k = 0$

Case 1 (distinct roots). If $r_1, \ldots, r_k$ are distinct, then $a_n = A_1 r_1^n + \cdots + A_k r_k^n$.

Case 2 (repeated roots). If $r$ has multiplicity $m$The contribution is $(A_1 + A_2 n + \cdots + A_m n^{m-1}) r^n$.

Problem. Solve $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1$, $a_1 = 4$.

Solution. Characteristic equation: $r^2 - 5r + 6 = 0$Giving $r_1 = 2$, $r_2 = 3$.

$a_n = A \cdot 2^n + B \cdot 3^n$.

From initial conditions: $a_0 = A + B = 1$ $a_1 = 2A + 3B = 4$

Solving: $B = 2$, $A = -1$. So $a_n = -2^n + 2 \cdot 3^n = 2 \cdot 3^n - 2^n$. $\blacksquare$

Worked Example. Solve $a_n = 4a_{n-1} - 4a_{n-2}$ with $a_0 = 1$, $a_1 = 6$.

The generating function of a sequence $\{a_n\}$ is

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

Example. The generating function for $a_n = 1$ (all ones) is $G(x) = 1/(1-x)$.

Example. The generating function for $a_n = r^n$ is $G(x) = 1/(1 - rx)$.

Generating functions can solve recurrences by converting them to algebraic equations in $G(x)$ Then extracting coefficients.

Worked Example. Use generating functions to solve the Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ With $F_0 = 0$, $F_1 = 1$.

Worked Example. Use generating functions to solve $a_n = 2a_{n-1} + 1$ with $a_0 = 0$.

:::caution Common Pitfall Generating functions are formal power series; they may not converge for any $x \neq 0$. Convergence Is irrelevant for combinatorial applications — the series is manipulated algebraically.

The Master Theorem provides asymptotic solutions to recurrences of the form

$T(n) = a\,T(n/b) + f(n)$

Where $a \geq 1$, $b \gt 1$ are constants and $f(n)$ is asymptotically positive. Define c_{\mathrm{crit{}} = \log_b a (the critical exponent).

Theorem 6.1 (Master Theorem). Let $T(n)$ be defined as above.

Case 1: If $f(n) = O(n^c)$ for some c \lt c_{\mathrm{crit{}}Then T(n) = \Theta(n^{c_{\mathrm{crit{}}}).

Case 2: If f(n) = \Theta(n^{c_{\mathrm{crit{}}} \log^k n) for some $k \geq 0$Then T(n) = \Theta(n^{c_{\mathrm{crit{}}} \log^{k+1} n).

Case 3: If $f(n) = \Omega(n^c)$ for some c \gt c_{\mathrm{crit{}}And $a\,f(n/b) \leq \delta\, f(n)$ For some $\delta \lt 1$ and sufficiently large $n$ (the regularity condition), then $T(n) = \Theta(f(n))$.

Worked Example. Solve $T(n) = 3T(n/2) + n^2$.

Worked Example. Solve $T(n) = 2T(n/2) + n$.

Worked Example. Solve $T(n) = 4T(n/2) + n$.

Proof sketch of the Master Theorem. Expand the recurrence tree. At level $j$ (root is level 0), There are $a^j$ subproblems, each of size $n/b^j$Each contributing $f(n/b^j)$ work. The tree has $\log_b n$ levels, with a^{\log_b n} = n^{c_{\mathrm{crit{}}} leaves. The total work is

T(n) = \Theta\!\left(n^{c_{\mathrm{crit}}\right) + \sum_{j=0}^{\log_b n - 1} a^j \, f(n/b^j)}

• Case 1: $f(n) = O(n^c)$ with c \lt c_{\mathrm{crit{}}. The sum is dominated by the leaves, giving T(n) = \Theta(n^{c_{\mathrm{crit{}}}).
• Case 2: f(n) = \Theta(n^{c_{\mathrm{crit{}}} \log^k n). Each level contributes the same order, with $\log_b n$ levels, giving T(n) = \Theta(n^{c_{\mathrm{crit{}}} \log^{k+1} n).
• Case 3: $f(n) = \Omega(n^c)$ with c \gt c_{\mathrm{crit{}}. The root level dominates, giving $T(n) = \Theta(f(n))$. The regularity condition $a\,f(n/b) \leq \delta\,f(n)$ ensures the root dominates all levels below. The Master Theorem does not apply to recurrences like $T(n) = T(n-1) + n$ (not of the form $a\,T(n/b) + f(n)$). Also, if $f(n)$ falls between cases (e.g., $f(n) = n \log n$ with c_{\mathrm{crit{}} = 1), the Master Theorem does not apply and the Akra—Bazzi method should be used Instead. :::