Key Concepts of Recurrence Relations

Why This Matters

Recurrence relations describe sequences where each term depends on previous ones. They show up everywhere in discrete math, from counting problems to algorithm analysis. You're expected to recognize different types of recurrences, choose the right solving technique, and connect these structures to combinatorial interpretations like partitions, paths, and counting arguments.

Don't just memorize formulas. For each concept below, know what type of recurrence it represents, which solving method applies, and what combinatorial structures it counts. Exam questions often ask you to set up a recurrence from a word problem, solve it using an appropriate technique, or explain why a particular sequence satisfies a given relation.

---

Foundational Structures: Linear Recurrences

These are the core recurrences where each term is a linear combination of previous terms. Linearity means solutions can be added together to form new solutions (superposition), which is what makes the characteristic equation method work.

Linear Recurrence Relations

• General form: $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$ where the coefficients $c_i$ are constants
• Order refers to how many previous terms are used. A second-order recurrence uses $a_{n-1}$ and $a_{n-2}$
• Initial conditions must be specified for the first $k$ terms to uniquely determine the sequence. Without them, you get a family of solutions, not a specific one

Homogeneous Recurrence Relations

A homogeneous recurrence has the form $a_n = c_1 a_{n-1} + \ldots + c_k a_{n-k}$ with nothing extra added on the right side. The word "homogeneous" just means there's no standalone function of $n$ tacked on.

• Characteristic polynomial is your primary solving tool: find its roots to construct the general solution
• General solution is a linear combination of terms based on those roots, adjusted for multiplicity if roots repeat (more on this below)

Non-Homogeneous Recurrence Relations

An additional function $f(n)$ appears on the right: $a_n = c_1 a_{n-1} + \ldots + c_k a_{n-k} + f(n)$.

• Solution structure combines the homogeneous solution (solve as if $f(n) = 0$) with a particular solution that accounts for $f(n)$
• Method of undetermined coefficients works when $f(n)$ is polynomial, exponential, or a combination. You guess a form for the particular solution, plug it in, and solve for the unknown constants. If your guess overlaps with a homogeneous solution, multiply by $n$ until it no longer does

---

Simple Patterns: Arithmetic and Geometric Sequences

These are special cases of first-order linear recurrences with clean closed forms. They're the building blocks you'll recognize inside more complex recurrences.

Arithmetic Sequences

• Constant difference $d$ between consecutive terms: $a_n = a_{n-1} + d$, with closed form $a_n = a_1 + (n-1)d$
• Sum formula: $S_n = \frac{n}{2}(2a_1 + (n-1)d)$, which comes from pairing the first and last terms
• The closed form is a linear function of $n$, so if you plot the sequence, you get a straight line

Geometric Sequences

• Constant ratio $r$ between consecutive terms: $a_n = r \cdot a_{n-1}$, with closed form $a_n = a_1 r^{n-1}$
• Sum formula: $S_n = a_1 \frac{1 - r^n}{1 - r}$ for $r \neq 1$
• Growth is exponential: the sequence grows if $|r| > 1$ and decays if $|r| < 1$

---

Solving Techniques: From Equations to Closed Forms

These methods transform recurrences into explicit formulas. Each technique has its sweet spot, and knowing when to apply which method is half the battle.

Characteristic Equation Method

This is the go-to method for constant-coefficient linear homogeneous recurrences.

1. Substitute $a_n = r^n$ into the recurrence and divide through by the lowest power of $r$. This gives you a polynomial equation in $r$ (the characteristic equation).
2. Solve the characteristic polynomial for its roots.
3. Build the general solution based on root types:
   • Distinct real roots $r_1, r_2, \ldots$: solution is $a_n = c_1 r_1^n + c_2 r_2^n + \ldots$
   • Repeated root $r$ with multiplicity $m$: contributes terms $c_1 r^n + c_2 n r^n + c_3 n^2 r^n + \ldots + c_m n^{m-1} r^n$
   • Complex roots $\alpha \pm \beta i$: yield terms involving $|\text{modulus}|^n \cos(n\theta)$ and $|\text{modulus}|^n \sin(n\theta)$
4. Apply initial conditions to solve for the constants $c_i$

Generating Functions for Solving Recurrences

• Power series encoding: define $G(x) = \sum_{n=0}^{\infty} a_n x^n$, then use the recurrence to turn this into an algebraic equation in $G(x)$
• Solve for $G(x)$ as a closed-form expression (usually a rational function)
• Extract coefficients via partial fractions or known series expansions to recover the sequence terms

This approach is powerful for recurrences where the characteristic method gets messy, especially convolution-type recurrences like the one for Catalan numbers.

Solving Recurrences Using Iteration

• Unroll the recurrence step-by-step: substitute the expression for $a_{n-1}$, then for $a_{n-2}$, and so on
• Spot the pattern that emerges, then write a conjectured closed form
• Prove your conjecture by induction

This method is best for simple cases or for building intuition before applying a more formal technique. For example, unrolling $T(n) = 2T(n-1) + 1$ quickly reveals a geometric series.

---

Combinatorial Counting Sequences

These recurrences arise from counting problems and have deep combinatorial interpretations. Understanding why the recurrence holds is often more important than memorizing the formula.

Fibonacci Sequence

• Recurrence: $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$
• Binet's formula: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2}$, derived via the characteristic equation with roots $\phi$ and $\psi$
• Combinatorial interpretation: $F_n$ counts the number of ways to tile a $1 \times n$ board with $1 \times 1$ squares and $1 \times 2$ dominoes. The recurrence follows because the first piece is either a square (leaving $n-1$ spaces) or a domino (leaving $n-2$ spaces)

Catalan Numbers

• Recurrence: $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ with $C_0 = 1$. This is a convolution-type recurrence, reflecting how a structure splits into two independent substructures
• Closed form: $C_n = \frac{1}{n+1}\binom{2n}{n}$
• Counts many things: valid arrangements of $n$ pairs of parentheses, full binary trees with $n+1$ leaves, triangulations of a convex $(n+2)$-gon, non-crossing partitions, and Dyck paths of length $2n$. Know at least three of these

Binomial Coefficients Recurrence

• Pascal's identity: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
• Combinatorial proof: to choose $k$ items from $n$, pick a specific element. Either it's included (then choose $k-1$ from the remaining $n-1$) or it's excluded (choose all $k$ from the remaining $n-1$)
• Base cases: $\binom{n}{0} = \binom{n}{n} = 1$ anchor the recursion

Stirling Numbers Recurrence

Stirling numbers of the second kind $S(n,k)$ count the number of ways to partition a set of $n$ elements into exactly $k$ non-empty subsets.

• Recurrence: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$
• Why it works: consider element $n$. Either it joins one of the $k$ existing subsets ($k$ choices, applied to a partition of the first $n-1$ elements into $k$ subsets) or it forms a new singleton subset (partition the first $n-1$ elements into $k-1$ subsets)
• Base cases: $S(0,0) = 1$, $S(n,0) = 0$ for $n > 0$, $S(n,n) = 1$

---

Algorithm Analysis: Divide-and-Conquer

These recurrences describe computational complexity and appear at the intersection of combinatorics and computer science. The structure of the recurrence reflects how an algorithm breaks a problem into subproblems.

Divide-and-Conquer Recurrences

• Standard form: $T(n) = aT(n/b) + f(n)$, meaning the algorithm splits the problem into $a$ subproblems each of size $n/b$, with $f(n)$ work to split and combine
• Examples: merge sort gives $T(n) = 2T(n/2) + O(n)$; binary search gives $T(n) = T(n/2) + O(1)$
• Analysis goal: determine asymptotic growth. Is it $O(n)$, $O(n \log n)$, or $O(n^2)$?

Master Theorem

The Master Theorem gives you a shortcut for recurrences of the form $T(n) = aT(n/b) + f(n)$. The key quantity is $n^{\log_b a}$, which represents the cost if all the work were done at the leaves of the recursion tree.

• Case 1: If $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$, the leaf work dominates: $T(n) = \Theta(n^{\log_b a})$
• Case 2: If $f(n) = \Theta(n^{\log_b a})$, work is evenly spread across levels: $T(n) = \Theta(n^{\log_b a} \log n)$
• Case 3: If $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ (and a regularity condition holds), the top-level work dominates: $T(n) = \Theta(f(n))$

For merge sort, $a = 2$, $b = 2$, so $n^{\log_2 2} = n$. Since $f(n) = O(n)$, this is Case 2, giving $T(n) = \Theta(n \log n)$.

Tower of Hanoi Recurrence

• Recurrence: $T(n) = 2T(n-1) + 1$ with $T(1) = 1$. The logic: move $n-1$ disks off the largest, move the largest, then move $n-1$ disks back on top
• Closed form: $T(n) = 2^n - 1$, which you can derive by iteration (unrolling reveals a geometric series $1 + 2 + 4 + \ldots + 2^{n-1}$) or by the characteristic equation method
• This is a classic example of a subtractive recurrence ($T(n-1)$, not $T(n/b)$) with an exponential solution

---

Quick Reference Table

---

Self-Check Questions

1. Both the Fibonacci sequence and the Tower of Hanoi satisfy second-order recurrences. What structural difference explains why Fibonacci grows roughly as $\phi^n / \sqrt{5}$ (where $\phi \approx 1.618$) while the Tower of Hanoi grows as $2^n$? (Hint: look at the characteristic roots.)

2. Given the recurrence $a_n = 3a_{n-1} - 2a_{n-2} + 5$, identify whether it's homogeneous or non-homogeneous, and outline which solving technique you'd apply first.

3. Compare and contrast Pascal's identity for binomial coefficients with the Stirling numbers recurrence. What combinatorial principle underlies both, and how do their interpretations differ?

4. If you need to find a closed form for $C_n$ (Catalan numbers) starting from the recurrence, which solving method would you choose and why? What makes this recurrence harder than Fibonacci?

5. The Master Theorem applies to recurrences of the form $T(n) = aT(n/b) + f(n)$. Explain why it cannot be directly applied to the Tower of Hanoi recurrence, and describe what alternative approach you'd use instead.