Recurrence Relations | Computer Science

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$.

flowchart TD
    A[6_Recurrence Relations] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Recurrence relations define sequences where each term depends on previous terms. They logically arise in divide-and-conquer algorithms (binary search: T(n) = T(n/2) + O(1)). Solving recurrences via substitution, recursion trees, or the Master theorem determines algorithm time complexity. Linear recurrences with constant coefficients have closed-form solutions using characteristic equations, connecting discrete math to continuous analysis.

Incorrect characteristic equation. For a recurrence $a_n + c_1 a_{n-1} + \cdots + c_k a_{n-k} = 0$, the characteristic equation is $r^k + c_1 r^{k-1} + \cdots + c_k = 0$. A common error is using the wrong signs on the coefficients. For $a_n = 5a_{n-1} - 6a_{n-2}$, the characteristic equation is $r^2 - 5r + 6 = 0$, not $r^2 + 5r - 6 = 0$.

Misapplying the Master Theorem. The Master Theorem does not apply to recurrences that are not of the form $T(n) = aT(n/b) + f(n)$. For example, $T(n) = T(n-1) + n$ cannot be solved with the Master Theorem. Also, if $f(n)$ falls between cases (e.g., $f(n) = n \log n$ with critical exponent 1), the theorem does not apply.

Forgetting repeated roots. When the characteristic equation has a repeated root $r$ with multiplicity $m$, the general solution includes terms $(A_1 + A_2 n + \cdots + A_m n^{m-1}) r^n$, not just $A r^n$. Students often omit the polynomial factor, leading to incorrect solutions for recurrences like $a_n = 4a_{n-1} - 4a_{n-2}$.

• [[1-algorithms/algorithm-design]] - Divide-and-conquer recurrences

• [[1-algorithms/complexity-theory]] - Complexity analysis

• [[1-discrete-mathematics/4_combinatorics]] - Counting sequences

• [[1-algorithms/data-structures]] - Recursive data structures

• Discrete Mathematics

• Algorithm Implementation

• Discrete Mathematics
• Propositional and Predicate Logic
• Sets, Relations, and Functions