Recurrence Relations

Linear Recurrences

A sequence is defined recurrently: $a(n)$ is expressed in terms of $a(n-1), ..., a(n-k)$.

Fibonacci numbers: $F(n) = F(n-1) + F(n-2)$, $F(0) = 0$, $F(1) = 1$.

Characteristic equation: $x^2 = x + 1$. Roots: $\varphi = \frac{1+\sqrt{5}}{2}$ (golden ratio), $\psi = \frac{1-\sqrt{5}}{2}$.

Binet's formula: $F(n) = \frac{\varphi^n - \psi^n}{\sqrt{5}}$.

General Method

For a homogeneous linear recurrence $a(n) = c_1a(n-1) + \ldots + c_k a(n-k)$:

1. Characteristic equation: $x^k = c_1x^{k-1} + \ldots + c_k$.
2. If the roots $x_1, ..., x_k$ are distinct: $a(n) = \alpha_1 x_1^n + \ldots + \alpha_k x_k^n$.
3. Coefficients are obtained from initial conditions.

For repeated roots $x_i$ of multiplicity $m_i$: the term $x_i^n(\alpha_0 + \alpha_1 n + \ldots + \alpha_{m_i-1} n^{m_i-1})$ appears.

Master Theorem

For $T(n) = aT(n/b) + f(n)$ ("divide and conquer" recurrences):

If $f(n) = O(n^{\log_b a - \varepsilon}) \rightarrow T(n) = \Theta(n^{\log_b a})$. If $f(n) = \Theta(n^{\log_b a}) \rightarrow T(n) = \Theta(n^{\log_b a} \log n)$. If $f(n) = \Omega(n^{\log_b a + \varepsilon}) \rightarrow T(n) = \Theta(f(n))$.

Application: MergeSort $T(n) = 2T(n/2) + \Theta(n)$: $a = 2$, $b = 2$, $\log_b a = 1$, $f(n) = \Theta(n) \rightarrow T(n) = \Theta(n \log n)$.

Linear Recurrences with Repeated Roots

When the characteristic equation has repeated roots, the solution formula becomes more complicated. For example, for $a(n) = 4a(n-1) - 4a(n-2)$ the characteristic equation $x^2 - 4x + 4 = (x-2)^2 = 0$ has root $x=2$ with multiplicity 2. Solution: $a(n) = (C_1 + C_2 n)\cdot 2^n$. General principle: root $r_i$ of multiplicity $m_i$ yields terms $r_i^n \cdot p(n)$, where $p$ is a polynomial of degree $m_i-1$.

For nonhomogeneous recurrences $a(n) = f(a(n-1), ...) + g(n)$ the method of variation of constants or guessing a particular solution is used. If $g(n) = b^n \cdot p(n)$, a particular solution is of the form $b^n \cdot q(n)$ (or $n^k b^n q(n)$, if $b$ is a root of the characteristic equation with multiplicity $k$).

Recurrences and Combinatorial Interpretations

Catalan numbers: $C_n = \frac{C(2n,n)}{n+1}$. Recurrence: $C_0=1$, $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$. Generating function: $C(x) = \frac{1-\sqrt{1-4x}}{2x}$. Catalan numbers count: correct parenthetical sequences, non-triangular partitions of an n-gon, complete binary trees, Dyck paths.

Stirling numbers of the first kind $s(n,k)$—the number of permutations of $n$ elements with exactly $k$ cycles. Recurrence: $s(n,k) = (n-1),s(n-1, k) + s(n-1,k-1)$. Connection with generating functions: $\sum_k s(n,k)x^k = x(x-1)\ldots(x-n+1)$ (falling factorial).

Master Theorem: Boundary Cases and Generalizations

The standard master theorem is not directly applicable to logarithmic factors. Generalized master theorem (Akra-Bazzi): For $T(n) = \sum a_i T(n/b_i) + f(n)$: find $p$ from $\sum a_i/b_i^p = 1$, then $T(n) = \Theta(n^p (1 + \int_1^n \frac{f(t)}{t^{p+1}}dt))$. This covers uneven split.

Boundary case: $T(n) = 2T(n/2) + n \log n$—second case of the master theorem with a logarithm: $T(n) = \Theta(n \log^2 n)$. Applied in analysis of merge sort algorithms with an additional logarithmic factor in the merge.

Important algorithms and their complexities via recurrences: Strassen (matrix multiplication) $T(n) = 7T(n/2) + \Theta(n^2) \rightarrow O(n^{\log_2 7}) \approx O(n^{2.81})$. Binary search $T(n) = T(n/2) + O(1) \rightarrow O(\log n)$. Karatsuba (number multiplication) $T(n)=3T(n/2)+\Theta(n) \rightarrow O(n^{\log_2 3}) \approx O(n^{1.585})$.

Solving Linear Recurrences: An Algebraic View

Consider the space of sequences satisfying the recurrence $L_k(a_n) = 0$ (homogeneous case). This is a linear space, its basis consists of elementary solutions $r^n$ and $n^j r^n$ (for repeated roots). Formally: shift operator $E: (a_n) \rightarrow (a_{n+1})$, then the recurrence $a(n) = c_1 a(n-1) + \ldots + c_k a(n-k)$ is written as $(E^k - c_1 E^{k-1} - \ldots - c_k)a_n = 0$. The kernel of this operator is generated by the basis solutions.

For a system of recurrences $a_n = M \cdot a_{n-1}$ (where $a_n$ is a vector, $M$ is a matrix): $a_n = M^n \cdot a_0$. Fast exponentiation: $M^n$ in $O(k^3 \log n)$ operations ($k$ is the dimension). For Fibonacci numbers: $(F_n, F_{n-1}) = \begin{bmatrix}1&1\1&0\end{bmatrix}^n \cdot (F_1,F_0)$. This gives $F_n$ in $O(\log n)$ integer multiplications.

Recurrences in Algorithm Analysis: Nuances

Dynamic programming recurrences have a different structure. 0/1 Knapsack problem: $dp[i][w] = \max(dp[i-1][w], dp[i-1][w-w_i]+v_i)$. Time: $O(nW)$, not polynomial in input size (since $W$ can be exponentially large)—a "pseudopolynomial" algorithm. Longest Common Subsequence: $dp[i][j] = $ (if $s[i]=t[j]$): $1 + dp[i-1][j-1]$; (else): $\max(dp[i-1][j], dp[i][j-1])$. Solved in $O(nm)$—quadratic.

Divide-and-conquer recurrences are often fully solved by the master theorem, while DP recurrences—by table filling. This distinction is important: in divide and conquer, each sublevel processes disjoint parts, while in DP subproblems overlap—thus memoization/DP table saves time.

Dynamic Programming: Probabilistic Extensions

Probabilistic recurrence: Problem: $E[$minimum cost$]$ under random transitions $\rightarrow$ stochastic DP. Bellman equation for MDP: $V^(s) = \max_a { R(s,a) + \gamma \cdot \sum P(s'|s,a) \cdot V^(s') }$. Solved by value iteration or policy iteration. In DP on DAG: shortest path problem with probabilistic edges—expected path length.

Enumerative Combinatorics: Inclusion-Exclusion Principle

$|A_1 \cup A_2 \cup ... \cup A_n| = \sum |A_i| - \sum |A_i \cap A_j| + ... + (-1)^{n+1} |A_1 \cap ... \cap A_n|$. Applications: derangements problem $D(n) = n! \sum (-1)^k / k! \approx n! / e$; number of surjections $n \rightarrow m$: $\sum (-1)^k C(m,k)(m-k)^n$. The Möbius function on partially ordered sets—a generalization of inclusion-exclusion.

Numerical Example: Solving a Linear Recurrence

Problem: Solve: $a_n = 5a_{n-1} - 6a_{n-2}$ for $a_0 = 0$, $a_1 = 1$.

Step 1: Characteristic equation: $r^2 - 5r + 6 = 0$. Discriminant: $25 - 24 = 1$. Roots: $r_1 = 2$, $r_2 = 3$.

Step 2: General solution: $a_n = C_1 \cdot 2^n + C_2 \cdot 3^n$. Initial conditions: $a_0 = C_1 + C_2 = 0 \rightarrow C_2 = -C_1$. $a_1 = 2C_1 + 3C_2 = 2C_1 - 3C_1 = -C_1 = 1 \rightarrow C_1 = -1$, $C_2 = 1$.

Step 3: Solution: $a_n = 3^n - 2^n$. Checks: $a_2 = 9-4 = 5 = 5 \cdot 1 - 6 \cdot 0$ ✓; $a_3 = 27-8 = 19 = 5 \cdot 5 - 6 \cdot 1$ ✓.

Step 4: OGF: $A(x) = \frac{x}{1-5x+6x^2} = \frac{x}{(1-2x)(1-3x)} = -\frac{1}{1-2x} + \frac{1}{1-3x} \rightarrow a_n = 3^n - 2^n$ ✓. Asymptotics: $a_n \sim 3^n$ (the larger root dominates). The Möbius function satisfies $\mu * 1 = \varepsilon$ (recurrence on divisors)—a direct generalization of inclusion-exclusion via Möbius inversion formula: if $g(n) = \sum_{d|n} f(d)$, then $f(n) = \sum_{d|n} \mu(n/d) g(d)$.