7.4 Recurrence relations

Definition of recurrence relations

A recurrence relation defines a sequence where each term is calculated from one or more previous terms. Instead of giving you a direct formula for the $n$th term, it tells you how to build each term from the ones before it.

This idea shows up constantly in discrete math and computer science. Any time you break a problem into smaller versions of itself, you're thinking recursively, and recurrence relations give you the mathematical language to describe that process precisely.

Examples of recurrence relations

Every recurrence relation needs two things: a rule connecting terms, and initial conditions that anchor the sequence to specific starting values. Without initial conditions, the relation describes a whole family of sequences rather than one specific one.

• Fibonacci sequence: $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$, $F_1 = 1$. Each term is the sum of the two before it, giving 0, 1, 1, 2, 3, 5, 8, 13, ...
• Arithmetic sequence: $a_n = a_{n-1} + d$, where $d$ is the common difference. If $a_0 = 3$ and $d = 2$, you get 3, 5, 7, 9, ...
• Geometric sequence: $a_n = r \cdot a_{n-1}$, where $r$ is the common ratio. If $a_0 = 1$ and $r = 3$, you get 1, 3, 9, 27, ...
• Tower of Hanoi: $T_n = 2T_{n-1} + 1$ with $T_1 = 1$. Here $T_n$ counts the minimum number of moves needed to transfer $n$ disks. The sequence goes 1, 3, 7, 15, ... and the closed-form solution turns out to be $T_n = 2^n - 1$.

Importance in mathematics

• Recurrence relations model recursive processes in nature and computer science, from population growth to algorithmic complexity.
• They provide a bridge between a recursive description of a problem and a closed-form solution (a direct formula for the $n$th term).
• Analyzing algorithms almost always involves setting up and solving a recurrence.
• They lay the groundwork for more advanced tools like generating functions and difference equations.

Types of recurrence relations

Classifying a recurrence relation helps you pick the right solving technique. Three main distinctions matter: linear vs. nonlinear, homogeneous vs. nonhomogeneous, and the order of the relation.

Linear vs. nonlinear

A recurrence is linear if each term is a linear combination of previous terms (no squaring, multiplying terms together, etc.). A nonlinear recurrence involves nonlinear operations on previous terms.

• Linear example: $a_n = 2a_{n-1} + 3a_{n-2}$
• Nonlinear example: $a_n = a_{n-1}^2 + 1$

Linear relations are much friendlier to work with because they often have clean closed-form solutions. Nonlinear ones frequently require numerical methods or approximations. A classic nonlinear example is the logistic map $x_{n+1} = rx_n(1 - x_n)$, used in population dynamics, which can exhibit chaotic behavior depending on the value of $r$.

Homogeneous vs. nonhomogeneous

A linear recurrence is homogeneous if every term on the right side involves the sequence itself (no standalone constants or functions of $n$). If there's an extra term that doesn't depend on the sequence, it's nonhomogeneous.

• Homogeneous: $a_n = 3a_{n-1} - 2a_{n-2}$
• Nonhomogeneous: $a_n = 2a_{n-1} + n$

To solve a nonhomogeneous relation, you typically find the general solution of the homogeneous part first, then find a particular solution to the full equation, and add them together.

First-order vs. higher-order

The order of a recurrence is how far back it looks. A first-order relation depends only on the immediately preceding term; a second-order relation depends on the two preceding terms, and so on.

• First-order: $a_n = 2a_{n-1} + 1$ (needs 1 initial condition)
• Second-order: $a_n = a_{n-1} + a_{n-2}$ (needs 2 initial conditions)
• Third-order: $T_n = T_{n-1} + T_{n-2} + T_{n-3}$ (needs 3 initial conditions)

The order tells you exactly how many initial conditions you need to pin down a unique sequence. The Tribonacci sequence is a natural third-order generalization of Fibonacci.

Solving recurrence relations

Three main methods cover most situations you'll encounter. The right choice depends on the structure of the relation and what form of answer you need.

Iterative method (unrolling)

The most direct approach: repeatedly substitute the recurrence into itself until a pattern emerges.

Steps:

1. Write out $a_n$ in terms of $a_{n-1}$.
2. Replace $a_{n-1}$ using the recurrence to get $a_n$ in terms of $a_{n-2}$.
3. Keep substituting until you see a pattern.
4. Express the general term using that pattern.
5. Verify with your initial conditions.

Example: For $a_n = a_{n-1} + 2$ with $a_0 = 5$:

• $a_n = a_{n-1} + 2 = (a_{n-2} + 2) + 2 = a_{n-2} + 4$
• Continuing: $a_n = a_0 + 2n = 5 + 2n$

This method works well for simple relations but gets unwieldy for complex ones.

Characteristic equation method

This is the go-to technique for linear homogeneous recurrence relations with constant coefficients.

Steps:

1. Start with the recurrence (e.g., $a_n = 5a_{n-1} - 6a_{n-2}$).

2. Assume a solution of the form $a_n = r^n$ and substitute it in.

3. Divide through by $r^{n-2}$ (or the appropriate power) to get the characteristic equation: $r^2 - 5r + 6 = 0$.

4. Solve for $r$. Here you get $r = 2$ and $r = 3$.

5. The general solution is $a_n = A \cdot 2^n + B \cdot 3^n$, where $A$ and $B$ are constants.

6. Use initial conditions to solve for $A$ and $B$.

If the characteristic equation has a repeated root $r$, the general solution takes the form $a_n = (A + Bn)r^n$ instead.

Generating functions approach

This method transforms the recurrence into an algebraic equation involving a power series. You define $G(x) = \sum_{n=0}^{\infty} a_n x^n$, manipulate the equation to solve for $G(x)$ in closed form, then extract the coefficients to recover $a_n$.

Generating functions are particularly powerful for complex recurrences where the characteristic equation method doesn't directly apply, such as the Catalan number recurrence $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$. The tradeoff is that the algebra can get involved.

Applications in mathematics

Fibonacci sequence

Defined by $F_n = F_{n-1} + F_{n-2}$ with $F_0 = 0$ and $F_1 = 1$, the Fibonacci sequence is probably the most famous recurrence relation. It appears in spiral arrangements in plants (sunflower seed heads, pinecone scales) and connects to the golden ratio $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$. Specifically, the ratio $F_{n+1}/F_n$ approaches $\phi$ as $n$ grows.

Using the characteristic equation method, you can derive the closed-form Binet's formula: $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$, where $\psi = \frac{1-\sqrt{5}}{2}$.

Factorial function

The factorial is a first-order recurrence: $n! = n \times (n-1)!$ with $0! = 1$. It's fundamental in combinatorics for counting permutations and combinations. For instance, the number of ways to arrange $n$ distinct objects is exactly $n!$. The factorial also connects to the continuous gamma function, where $\Gamma(n+1) = n!$ for non-negative integers.

Binomial coefficients

The recurrence $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ is exactly the rule that builds Pascal's triangle: each entry is the sum of the two entries above it. Binomial coefficients count the number of ways to choose $k$ items from $n$, making them essential in probability and the binomial theorem for expanding $(a+b)^n$.

Recurrence relations in algorithms

Recurrence relations are the primary tool for analyzing the time complexity of recursive algorithms. If an algorithm calls itself on smaller inputs, you can write a recurrence for its running time and then solve it.

Divide-and-conquer algorithms

These algorithms split a problem into smaller subproblems, solve each recursively, and combine the results. The general form of their recurrence is $T(n) = aT(n/b) + f(n)$, where $a$ is the number of subproblems, $n/b$ is the size of each, and $f(n)$ is the cost of dividing and combining.

• Mergesort splits the array in half, sorts both halves, and merges: $T(n) = 2T(n/2) + O(n)$, which solves to $O(n \log n)$.
• Binary search eliminates half the input each step: $T(n) = T(n/2) + O(1)$, which solves to $O(\log n)$.

Dynamic programming

Dynamic programming solves problems by building up solutions to subproblems and storing results to avoid redundant computation. The underlying structure is almost always a recurrence relation.

Computing Fibonacci numbers naively with recursion takes exponential time because you recompute the same values over and over. With dynamic programming (storing each $F_k$ as you compute it), it drops to $O(n)$. The 0/1 knapsack problem uses the recurrence $dp[i][w] = \max(dp[i-1][w],\; dp[i-1][w-w_i] + v_i)$, where $w_i$ and $v_i$ are the weight and value of item $i$.

Analysis of recurrence relations

Big O notation

Big O notation describes the upper bound on a function's growth rate, giving you a way to compare algorithm efficiencies without worrying about constant factors. When you solve a recurrence like $T(n) = 2T(n/2) + O(n)$ and get $O(n \log n)$, that tells you mergesort's running time grows roughly proportional to $n \log n$ as the input size increases.

Time complexity analysis

Two widely used techniques for analyzing recurrences:

• Master Theorem: A formula that directly solves recurrences of the form $T(n) = aT(n/b) + f(n)$ by comparing $f(n)$ to $n^{\log_b a}$. It covers most standard divide-and-conquer recurrences.
• Recurrence tree method: You draw out the recursive calls as a tree, calculate the work done at each level, and sum across all levels. This gives a visual way to arrive at (or verify) the Big O bound.

Both methods are tools for getting from a recurrence to a closed-form complexity expression.

Advanced concepts

Systems of recurrence relations

Sometimes you have multiple sequences that depend on each other. For example, a predator-prey model might define the predator population $P_n$ in terms of both $P_{n-1}$ and the prey population $Q_{n-1}$, and vice versa. These systems can be solved using matrix methods (writing the system as a matrix equation and finding eigenvalues) or generating function techniques.

Asymptotic behavior

Asymptotic analysis studies what happens to a sequence as $n \to \infty$. Does it converge to a fixed value? Grow without bound? Oscillate? Techniques like characteristic root analysis and the ratio test help answer these questions. This matters for understanding whether iterative algorithms converge, whether population models reach equilibrium, and how fast sequences grow in the long run.

Recurrence relations vs. difference equations

Recurrence relations and difference equations are closely related and sometimes the terms are used interchangeably. The distinction is mostly one of notation and context.

Similarities and differences

• Both describe sequences where each term depends on previous terms.
• Recurrence relations typically use subscript notation: $a_n = f(a_{n-1}, a_{n-2}, \ldots)$
• Difference equations often use function notation: $f(n+1) = g(f(n), f(n-1), \ldots)$
• Difference equations are more common when bridging discrete and continuous models, since they parallel differential equations.

Conversion between forms

Converting between the two is straightforward. The recurrence $a_n = 2a_{n-1}$ becomes $f(n+1) = 2f(n)$ in difference equation form. Being comfortable with both notations lets you draw on techniques from either field and move between discrete and continuous frameworks when modeling real-world problems.

Computational tools

Software for solving recurrences

• Computer algebra systems like Mathematica, Maple, and SymPy can solve recurrences symbolically, giving you exact closed-form solutions.
• Programming languages like Python and R are useful for computing terms numerically and running simulations.
• Wolfram Alpha is a quick option for checking solutions to straightforward recurrences.

Visualization techniques

Plotting the terms of a sequence helps you spot growth patterns, convergence, or oscillation that might not be obvious from the formula alone. Cobweb diagrams are especially useful for first-order recurrences: they show graphically whether an iterative process converges to a fixed point or diverges. For systems of recurrences, phase plane plots reveal how two interrelated sequences evolve together over time.