Key Concepts of Recurrence Relations

Why This Matters

Recurrence relations are the backbone of algebraic combinatorics—they're how we describe sequences where each term depends on previous ones, and they show up everywhere from counting problems to algorithm analysis. You're being tested on your ability 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. Master the underlying principles, and you'll handle any variation they throw at you.

---

Foundational Structures: Linear Recurrences

These are your bread-and-butter recurrences where each term is a linear combination of previous terms. The key insight is that linearity allows us to use superposition—solutions can be added together to form new solutions.

Linear Recurrence Relations

• General form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \ldots + c_k a_{n-k}$—the coefficients $c_i$ are constants, and the relation is determined by $k$ previous terms
• 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

Homogeneous Recurrence Relations

• No extra terms—the recurrence has the form $a_n = c_1 a_{n-1} + \ldots + c_k a_{n-k}$ with nothing added on the right side
• Characteristic polynomial is your primary solving tool; find roots to construct the general solution
• General solution is a linear combination of terms based on the roots, adjusted for multiplicity if roots repeat

Non-Homogeneous Recurrence Relations

• Additional function $f(n)$ appears: $a_n = c_1 a_{n-1} + \ldots + c_k a_{n-k} + f(n)$
• Solution structure combines the homogeneous solution with a particular solution that handles $f(n)$
• Method of undetermined coefficients works when $f(n)$ is polynomial, exponential, or a combination—guess a form and solve for constants

---

Simple Patterns: Arithmetic and Geometric Sequences

These are special cases of first-order linear recurrences with elegant 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$, or equivalently $a_n = a_1 + (n-1)d$
• Sum formula $S_n = \frac{n}{2}(2a_1 + (n-1)d)$ comes from pairing first and last terms
• Linear growth—the closed form is a linear function of $n$, making these easy to identify graphically

Geometric Sequences

• Constant ratio $r$ between consecutive terms: $a_n = r \cdot a_{n-1}$, or equivalently $a_n = a_1 r^{n-1}$
• Sum formula $S_n = a_1 \frac{1 - r^n}{1 - r}$ for $r \neq 1$—memorize this; it appears constantly
• Exponential growth or decay depending on whether $|r| > 1$ or $|r| < 1$

---

Solving Techniques: From Equations to Closed Forms

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

Characteristic Equation Method

• Substitution $a_n = r^n$ converts the recurrence into a polynomial equation in $r$
• Root types matter—distinct real roots give terms like $c_1 r_1^n + c_2 r_2^n$; repeated roots introduce factors of $n$; complex roots yield trigonometric expressions
• Initial conditions determine the specific constants $c_i$ in your general solution

Generating Functions for Solving Recurrences

• Power series encoding $G(x) = \sum_{n=0}^{\infty} a_n x^n$ transforms the recurrence into an algebraic equation
• Algebraic manipulation lets you solve for $G(x)$ as a closed-form rational function
• Coefficient extraction via partial fractions or series expansion recovers the sequence terms—powerful for complex recurrences where characteristic methods get messy

Solving Recurrences Using Iteration

• Unrolling the recurrence step-by-step reveals patterns: substitute $a_{n-1}$, then $a_{n-2}$, and so on
• Pattern recognition leads to a conjectured closed form, which you then prove by induction
• Best for simple cases—use this when the recurrence has obvious structure or when you need intuition before applying formal methods

---

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$—the classic second-order homogeneous example
• Binet's formula $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ where $\phi = \frac{1+\sqrt{5}}{2}$, derived via characteristic equation
• Combinatorial interpretation—counts tilings, paths, and appears in nature; know at least one counting argument

Catalan Numbers

• Recurrence $C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$ with $C_0 = 1$—a convolution-type recurrence reflecting recursive structure
• Closed form $C_n = \frac{1}{n+1}\binom{2n}{n}$—memorize this; it's frequently tested
• Counts everything—valid parentheses, binary trees, triangulations, non-crossing partitions, Dyck paths; know at least three interpretations

Binomial Coefficients Recurrence

• Pascal's identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$—each entry is the sum of two entries above it
• Combinatorial proof—choosing $k$ from $n$ either includes or excludes a specific element
• 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 partitions of $n$ elements into $k$ non-empty subsets
• Recurrence $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$—the new element either joins an existing subset ($k$ choices) or forms its own
• 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 reflects how algorithms break problems into subproblems.

Divide-and-Conquer Recurrences

• Standard form $T(n) = aT(n/b) + f(n)$—split into $a$ subproblems of size $n/b$, with $f(n)$ overhead
• Examples include merge sort ($T(n) = 2T(n/2) + n$) and binary search ($T(n) = T(n/2) + 1$)
• Analysis goal is determining asymptotic growth—is it $O(n)$, $O(n \log n)$, or $O(n^2)$?

Master Theorem

• Three cases based on comparing $f(n)$ to $n^{\log_b a}$—this comparison determines which term dominates
• Case 1: if $f(n) = O(n^{\log_b a - \epsilon})$, then $T(n) = \Theta(n^{\log_b a})$
• Quick analysis—lets you solve common recurrences by inspection rather than full derivation; essential for algorithm complexity questions

Tower of Hanoi Recurrence

• Recurrence $T(n) = 2T(n-1) + 1$ with $T(1) = 1$—move $n-1$ disks, move the largest, move $n-1$ again
• Closed form $T(n) = 2^n - 1$—derive this by iteration or characteristic equation
• Classic example of a non-divide-and-conquer recurrence with exponential solution; great for practicing iteration method

---

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 polynomially in its closed form's dominant term while Tower of Hanoi grows exponentially?

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 an FRQ asks you 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 modification to your approach is needed.