Chapter 18: Recurrence Relations

"Now, here, you see, it takes all the running you can do, to keep in the same place." — Lewis Carroll, Through the Looking-Glass

Overview

Every recursive function you have ever written contains a hidden equation. When you write

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

you have not only defined a function — you have written down a relation that the output sequence must satisfy: the $n$-th value equals the sum of the two before it. That relation is a recurrence, and learning to read it, classify it, and solve it is the difference between running your code to find out how a sequence behaves and knowing in advance.

This matters to a programmer for two distinct reasons, and the chapter pursues both.

First, recurrences are how we count things that build on themselves. How many ways can you tile a $2 \times n$ board with dominoes? How many moves does it take to solve the Tower of Hanoi with $n$ disks? How many binary strings of length $n$ avoid two consecutive zeros? In each case the answer for $n$ is most naturally expressed in terms of the answer for smaller inputs. We set up the recurrence by thinking recursively about the structure of the problem, then solve it to get a clean formula.

Second — and this is the thread that runs straight into Chapter 19 — recurrences are how we measure the cost of recursive algorithms. The running time of merge sort obeys $T(n) = 2T(n/2) + O(n)$. The running time of binary search obeys $T(n) = T(n/2) + O(1)$. Before you can say "merge sort is $O(n \log n)$," someone has to solve that recurrence. This chapter teaches you to extract the recurrence from code and to solve the most important closed-form-friendly family by hand; Chapter 19 finishes the job for the divide-and-conquer recurrences with the Master Theorem.

There is also a long-running character in this book who finally gets the spotlight here: the Fibonacci sequence. We have defined it recursively (Chapter 6) and proven things about it by strong induction (Chapter 7). In this chapter we identify its recurrence as a member of a solvable family, and in Chapter 19 we will produce its astonishing closed form involving the golden ratio. By the end of this chapter you will understand why such a closed form must exist.

In this chapter you will learn to:

• State a recurrence relation precisely, including the initial conditions that pin down a unique sequence.
• Translate a self-referential counting problem (Hanoi, tilings, string-counting) into a recurrence.
• Classify a recurrence by linearity, homogeneity, and order, so you know which technique applies.
• Solve any linear homogeneous recurrence with constant coefficients via its characteristic equation — distinct roots and repeated roots alike.
• Handle a simple nonhomogeneous recurrence by finding a particular solution and adding it to the homogeneous one.
• Recognize the recurrence implied by a piece of recursive code, the first step in analyzing its cost.

Learning Paths

🏃 Fast Track: If you already write recurrences fluently, skim 18.1–18.2, then concentrate on 18.3 and 18.4 (the characteristic-equation method, including repeated roots) and 18.6 (code → recurrence). Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Set up each recurrence in 18.2 yourself before reading our derivation, and work every 🔄 Check Your Understanding. The characteristic-equation method in 18.4 rewards a slow first pass.

🔬 Deep Dive: After 18.4, prove that the general solution of a second-order linear homogeneous recurrence really is a two-parameter family (any solution is a linear combination of the two basic ones), and work through why the repeated-root case needs the extra factor of $n$. The exercise set Part E scaffolds this.

18.1 What is a recurrence?

Start with something you can see. Here is a sequence: $3, 7, 11, 15, 19, \dots$ You recognize it instantly — each term is the previous term plus 4. There are two completely different ways to write down "what this sequence is," and the gap between them is the subject of this entire chapter.

The first way is a closed form (also called an explicit formula): a rule that computes the $n$-th term directly from $n$. Here that rule is $a_n = 3 + 4n$ (with $a_0 = 3$). Plug in $n = 5$ and you get $a_5 = 23$ in one step, never touching the earlier terms.

The second way is a recurrence relation: a rule that computes the $n$-th term from one or more earlier terms. Here that rule is $a_n = a_{n-1} + 4$. To find $a_5$ this way you must already know $a_4$, which needs $a_3$, and so on, down to a starting value.

Definition. A recurrence relation for a sequence $\{a_n\}$ is an equation that expresses $a_n$, for all $n$ past some threshold, in terms of one or more of the preceding terms $a_0, a_1, \dots, a_{n-1}$. A value $a_n$ is a solution of the recurrence if substituting it (and its predecessors) satisfies the equation for every $n$ in range.

A recurrence on its own does not determine a sequence. The rule $a_n = a_{n-1} + 4$ is satisfied by $3, 7, 11, \dots$ but equally by $100, 104, 108, \dots$ and by $-2, 2, 6, \dots$. To pin down one sequence you must also specify where it starts.

Definition. The initial conditions of a recurrence are the explicitly given values of the earliest terms — enough of them to get the recurrence started. A recurrence that refers back $k$ terms (its order is $k$) needs $k$ initial conditions.

Put a recurrence and its initial conditions together and you have a complete, unambiguous specification of a sequence:

$$a_0 = 3, \qquad a_n = a_{n-1} + 4 \ \text{ for } n \ge 1.$$

This is exactly the shape of a recursive definition from Chapter 7 — a base case (the initial condition) plus a recursive rule (the recurrence). The two phrases name the same idea from two angles: a recursive definition emphasizes that we are defining the object; a recurrence relation emphasizes that we have an equation to solve.

🔗 Connection. In Chapter 11 you met sequences and learned to tell a closed-form description from a recursive one. A recurrence relation is the formal name for that recursive description. The work of this chapter — solving a recurrence — is the work of converting the recursive description back into a closed form, so you can compute $a_n$ without computing everything before it.

Why prefer one form over the other? It depends on what you want.

• A closed form lets you compute $a_n$ in (usually) constant time, compare growth rates, and prove exact bounds. $a_n = 3 + 4n$ tells you at a glance that the sequence is linear in $n$.
• A recurrence is almost always easier to write down from the structure of a problem. You rarely guess a closed form directly; you discover the recurrence by thinking recursively, then solve it.

The naive fib at the top of this chapter is a cautionary tale about computing straight from a recurrence. It re-solves the same subproblems exponentially many times — fib(50) makes over $2.5 \times 10^{10}$ calls. The closed form (Chapter 19) computes $F_{50}$ in a handful of operations. That gap between an unrolled recurrence and a solved one is not academic; it is the difference between a program that finishes and one that doesn't.

def a(n):
    """The sequence 3, 7, 11, ... defined by a recurrence."""
    if n == 0:          # initial condition
        return 3
    return a(n - 1) + 4 # recurrence relation

print([a(n) for n in range(6)])
# Expected output:
# [3, 7, 11, 15, 19, 23]

🔄 Check Your Understanding 1. The recurrence $a_n = 2a_{n-1}$ has many solutions. Give two different sequences that satisfy it, and say what extra information selects exactly one. 2. Is $a_n = a_{n-1} + a_{n-2}$ enough to determine a sequence? How many initial conditions does it need, and why?

Answers

1. $1, 2, 4, 8, \dots$ (with $a_0 = 1$) and $5, 10, 20, 40, \dots$ (with $a_0 = 5$) both satisfy $a_n = 2a_{n-1}$. A single initial condition $a_0$ selects exactly one. 2. Not by itself — it is a second-order recurrence (it reaches back two terms), so it needs two initial conditions, say $a_0$ and $a_1$. With $a_0 = 0, a_1 = 1$ you get Fibonacci; with $a_0 = 2, a_1 = 1$ you get the Lucas numbers.

18.2 Modeling with recurrences

The skill that pays off everywhere is setting up a recurrence from a problem description. The recipe is always the same: express a size-$n$ instance in terms of smaller instances, count the cost of the assembly, and read off the equation. Let's do three classic examples, each teaching a different flavor of the setup.

🧩 Productive Struggle. Before reading on, try one yourself: in how many ways can you write the integer $n$ as an ordered sum of 1s and 2s? (For $n = 3$: $1+1+1$, $1+2$, $2+1$ — three ways.) Find a recurrence by asking "what can the first part of the sum be?" You should land on a relation you recognize. Hold onto your answer — the binary-string example below uses the very same move, and the spaced review returns to it.

Example 1: The Tower of Hanoi

The puzzle: three pegs, and $n$ disks of distinct sizes stacked on the first peg, largest at the bottom. Move the whole stack to the third peg, moving one disk at a time, never placing a larger disk on a smaller one. Let $H_n$ be the minimum number of moves required.

💡 Intuition: Don't think about the individual moves — think about the one move that matters. To get the largest disk from peg 1 to peg 3, you must first get the other $n-1$ disks entirely out of the way (onto peg 2). Then move the big disk once. Then move those $n-1$ disks on top of it.

That insight is the recurrence. Moving $n-1$ disks (to peg 2, using peg 3 as spare) costs $H_{n-1}$ moves by definition. Moving the largest disk costs 1. Moving the $n-1$ disks back on top costs $H_{n-1}$ again. So:

$$H_n = 2 H_{n-1} + 1, \qquad H_0 = 0.$$

The initial condition $H_0 = 0$ says zero disks take zero moves. Unrolling a few terms: $H_1 = 1$, $H_2 = 3$, $H_3 = 7$, $H_4 = 15$. The pattern $1, 3, 7, 15, \dots$ should make you suspect $H_n = 2^n - 1$ — and in 18.5 we will derive that, not just guess it.

🔗 Connection. A legend (Tier 3 — illustrative; the "priests of Brahma" framing is folklore popularized by the puzzle's 19th-century inventor) says monks are moving 64 golden disks, and the world ends when they finish. At $H_{64} = 2^{64} - 1 \approx 1.8 \times 10^{19}$ moves and one move per second, that's about 585 billion years. The recurrence doesn't just count — it tells you the cost is exponential, and exponential costs are the wall every programmer eventually hits.

Example 2: Tiling a $2 \times n$ board

The problem: in how many ways can you tile a $2 \times n$ rectangular board using $1 \times 2$ dominoes (each domino covers two adjacent squares, placed either horizontally or vertically)? Call this count $t_n$.

The setup, by structure. Look at the leftmost column of the board. There are exactly two ways to cover it. Either you place one vertical domino filling that whole column — leaving a $2 \times (n-1)$ board to tile in $t_{n-1}$ ways — or you place two horizontal dominoes, whose right halves stick into the next column, filling the first two columns entirely and leaving a $2 \times (n-2)$ board, tileable in $t_{n-2}$ ways. Those two cases are mutually exclusive and exhaustive.

By the sum rule (Chapter 15), the total is the sum:

$$t_n = t_{n-1} + t_{n-2}, \qquad t_1 = 1, \quad t_2 = 2.$$

That is the Fibonacci recurrence. Checking: $t_1 = 1$ (one vertical domino), $t_2 = 2$ (two verticals, or two horizontals), $t_3 = 3$, $t_4 = 5$. Indeed $t_n = F_{n+1}$ — the domino tilings of a $2 \times n$ board are Fibonacci numbers, shifted by one. We will exploit this in the spaced review.

🔗 Connection. This is the Fibonacci anchor of the book showing up where you least expect it. The same recurrence governs rabbit populations (Fibonacci's original 1202 problem), domino tilings, the number of binary strings with no two consecutive 1s, and the number of ways to climb $n$ stairs taking 1 or 2 steps at a time. One recurrence, many disguises. Chapter 19 gives its closed form.

Example 3: Binary strings avoiding "00"

How many binary strings of length $n$ contain no two consecutive zeros? Call it $s_n$.

The setup, by the last symbol. Classify the strings by how they end. A valid string of length $n$ either ends in 1 — in which case the first $n-1$ symbols form any valid string of length $n-1$ ($s_{n-1}$ of them) — or it ends in 0, and then the symbol before that 0 must be a 1 (otherwise we'd have 00), so it ends in 10, and the first $n-2$ symbols form any valid string of length $n-2$ ($s_{n-2}$ of them).

$$s_n = s_{n-1} + s_{n-2}, \qquad s_1 = 2, \quad s_2 = 3.$$

(The two length-1 strings 0 and 1 are both valid; the length-2 strings are 01, 10, 11 — three of them, since only 00 is forbidden.) Fibonacci again, shifted differently: $s_n = F_{n+2}$.

These three examples teach the two universal setup moves, and almost every recurrence you'll build uses one of them:

🔄 Check Your Understanding 1. Set up (don't solve) a recurrence for the number of ways to climb $n$ stairs if you can take 1, 2, or 3 steps at a time. How many initial conditions does it need? 2. In the Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$, what does the lone "$+1$" represent, and why is the coefficient on $H_{n-1}$ a 2 rather than a 1?

Answers

1. $c_n = c_{n-1} + c_{n-2} + c_{n-3}$ (your last move was a 1-, 2-, or 3-step). It reaches back three terms, so it is third-order and needs three initial conditions (e.g., $c_0 = 1, c_1 = 1, c_2 = 2$). This is the "Tribonacci" recurrence. 2. The "$+1$" is the single move of the largest disk. The coefficient 2 is because the $n-1$ smaller disks must be moved twice — once off the big disk and once back on top of it.

18.3 Linear homogeneous recurrences

Most of this chapter solves one well-behaved family, because that family is solvable by a clean, mechanical method and it covers Fibonacci, the examples above, and a great deal more. Defining the family precisely tells you exactly when the method applies.

Definition. A linear homogeneous recurrence relation with constant coefficients of order $k$ is a recurrence of the form $$a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k},$$ where $c_1, c_2, \dots, c_k$ are constants (not depending on $n$) with $c_k \ne 0$.

Unpack the three adjectives, because each one is a real restriction and you must be able to spot a violation:

• Linear: each term $a_{n-i}$ appears to the first power and is multiplied only by a constant. No $a_{n-1}^2$, no $a_{n-1} a_{n-2}$, no $\sqrt{a_{n-1}}$, no $n \cdot a_{n-1}$ (that last has a variable coefficient, which is also disallowed by "constant coefficients").
• Homogeneous: every term contains some $a_{n-i}$. There is no standalone term that depends only on $n$ (or is a nonzero constant). The "$+1$" in the Hanoi recurrence makes it nonhomogeneous — we'll handle that kind in 18.5.
• Constant coefficients: the $c_i$ are fixed numbers.
• Order $k$: the recurrence reaches back exactly $k$ terms (the deepest one, $a_{n-k}$, has a nonzero coefficient). It therefore needs $k$ initial conditions.

⚠️ Common Pitfall: "linear" is about the $a$'s, not about $n$. A recurrence is linear when it is a linear combination of previous terms. It says nothing about how the terms grow — a linear homogeneous recurrence like $a_n = 2a_{n-1}$ produces exponential growth ($2^n$). Don't confuse "linear recurrence" with "linear growth."

Let's sort some recurrences against the definition; this classification is the first thing you do when you meet a new recurrence, because it tells you which tool to reach for.

💡 Intuition: why "homogeneous linear with constant coefficients" is special. Equations of this shape have a magic property: if you have two sequences that each satisfy the recurrence, then any linear combination of them — add them, scale them — also satisfies it. (You'll verify this in the exercises; it follows directly from the recurrence being a linear combination of terms with constant coefficients.) That "solutions can be superposed" property is exactly what lets us build every solution out of a few basic building blocks. It is the same reason linear differential equations are tractable, and it is why this family, and not the nonlinear ones, gets a tidy formula.

🔄 Check Your Understanding 1. Classify $a_n = 5a_{n-2} - a_{n-4}$: is it linear homogeneous with constant coefficients? What is its order, and how many initial conditions does it need? 2. Why is $a_n = a_{n-1} + n$ not homogeneous, and why is that a problem for the method we're about to learn?

Answers

1. Yes — it's a linear combination of previous terms with constant coefficients $(5$ and $-1)$ and no standalone term. The deepest reach is $a_{n-4}$, so it is order 4 and needs four initial conditions. (The missing $a_{n-1}, a_{n-3}$ just have coefficient 0.) 2. The "$+n$" is a standalone term that depends on $n$ but is not a multiple of any previous $a$. The characteristic-equation method in 18.4 works only when every term carries an $a_{n-i}$; the extra $+n$ requires the particular-solution technique of 18.5.

18.4 The characteristic equation

Now the payoff: a mechanical method that turns a linear homogeneous recurrence into an algebra problem. We'll develop it for order 2 (which covers Fibonacci and almost everything you'll meet), then state the general pattern.

The idea: guess a geometric solution

The strategy, in one sentence. Guess that the solution is a geometric sequence $a_n = r^n$, substitute, and see what value of $r$ the recurrence forces. The reason this is a smart guess: a geometric sequence is the simplest thing whose "next term" is a constant multiple of the current one, which is exactly the kind of self-similar behavior a constant-coefficient recurrence rewards.

Take the general second-order linear homogeneous recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$. Try $a_n = r^n$ for some nonzero $r$. Substituting:

$$r^n = c_1 r^{n-1} + c_2 r^{n-2}.$$

Divide through by $r^{n-2}$ (legal because $r \ne 0$):

$$r^2 = c_1 r + c_2, \qquad \text{i.e.} \qquad r^2 - c_1 r - c_2 = 0.$$

That quadratic is the heart of the whole method.

Definition. The characteristic equation of the linear homogeneous recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ is $$r^2 - c_1 r - c_2 = 0.$$ Its roots are the characteristic roots. (For order $k$, the characteristic equation is $r^k - c_1 r^{k-1} - c_2 r^{k-2} - \cdots - c_k = 0$ — replace each $a_{n-i}$ with $r^{k-i}$.)

So $r^n$ is a solution of the recurrence exactly when $r$ is a root of the characteristic equation. Each root gives one geometric solution. The superposition property from 18.3 then says any linear combination of those geometric solutions is also a solution — and (a theorem we'll use, proven in the Deep Dive exercises) for a second-order recurrence every solution arises this way. We just need the initial conditions to fix the combination.

Case 1: distinct roots

Theorem (distinct roots). Suppose the characteristic equation $r^2 - c_1 r - c_2 = 0$ has two distinct roots $r_1 \ne r_2$. Then the solutions of $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ are exactly the sequences $$a_n = \alpha\, r_1^{\,n} + \beta\, r_2^{\,n},$$ for constants $\alpha, \beta$ determined by the initial conditions.

The strategy before the proof. We must show two things: (1) every such combination is a solution (this is superposition — easy), and (2) the constants $\alpha, \beta$ can always be chosen to match any two initial conditions (this needs $r_1 \ne r_2$). We'll prove direction (1) cleanly and show why (2) works; the full "these are all the solutions" claim is the Deep Dive.

Proof. (Direction: any such $a_n$ is a solution.) Fix roots $r_1, r_2$ and constants $\alpha, \beta$, and let $a_n = \alpha r_1^n + \beta r_2^n$. Because $r_1$ is a root, $r_1^2 = c_1 r_1 + c_2$, and multiplying by $r_1^{n-2}$ gives $r_1^n = c_1 r_1^{n-1} + c_2 r_1^{n-2}$; likewise $r_2^n = c_1 r_2^{n-1} + c_2 r_2^{n-2}$. Then $$c_1 a_{n-1} + c_2 a_{n-2} = c_1(\alpha r_1^{n-1} + \beta r_2^{n-1}) + c_2(\alpha r_1^{n-2} + \beta r_2^{n-2})$$ $$= \alpha(c_1 r_1^{n-1} + c_2 r_1^{n-2}) + \beta(c_1 r_2^{n-1} + c_2 r_2^{n-2}) = \alpha r_1^n + \beta r_2^n = a_n.$$ So $a_n$ satisfies the recurrence for every $n \ge 2$.

(Matching the initial conditions.) Given $a_0$ and $a_1$, we need $\alpha + \beta = a_0$ and $\alpha r_1 + \beta r_2 = a_1$. This is a $2 \times 2$ linear system in $\alpha, \beta$; its determinant is $r_2 - r_1$, which is nonzero precisely because the roots are distinct. So a unique $\alpha, \beta$ exists. $\blacksquare$

Let's run the method end to end.

Worked example. Solve $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1$, $a_1 = 4$.

1. Characteristic equation: $r^2 - 5r + 6 = 0$. (Move everything to one side: from $a_n = 5a_{n-1} - 6a_{n-2}$ we read $c_1 = 5, c_2 = -6$, giving $r^2 - 5r - (-6) = r^2 - 5r + 6$.)
2. Roots: $r^2 - 5r + 6 = (r-2)(r-3)$, so $r_1 = 2$, $r_2 = 3$ — distinct.
3. General solution: $a_n = \alpha \cdot 2^n + \beta \cdot 3^n$.
4. Use initial conditions: $n=0$ gives $\alpha + \beta = 1$; $n=1$ gives $2\alpha + 3\beta = 4$. Subtract twice the first from the second: $\beta = 2$, hence $\alpha = -1$.
5. Closed form: $a_n = -2^n + 2 \cdot 3^n$.

Check it independently: $a_2$ from the formula is $-4 + 2\cdot 9 = 14$; from the recurrence, $5(4) - 6(1) = 14$. ✅ And $a_3$: formula gives $-8 + 2\cdot 27 = 46$; recurrence gives $5(14) - 6(4) = 46$. ✅

def closed(n):   # solved form
    return -2**n + 2 * 3**n

def rec(n):      # straight from the recurrence
    if n == 0: return 1
    if n == 1: return 4
    return 5 * rec(n - 1) - 6 * rec(n - 2)

print([closed(n) for n in range(6)])
print([rec(n)    for n in range(6)])
# Expected output:
# [1, 4, 14, 46, 146, 454]
# [1, 4, 14, 46, 146, 454]

The two lists agree — the closed form computes in a constant number of operations what the recurrence computes by unrolling. (We hand-checked $n = 0..3$ above; $a_4 = -16 + 2\cdot81 = 146$ and $a_5 = -32 + 2\cdot 243 = 454$ extend the pattern, and the recurrence gives $5\cdot46 - 6\cdot14 = 146$, $5\cdot146 - 6\cdot46 = 454$.)

Case 2: a repeated root

What if the characteristic equation has a double root, $r^2 - c_1 r - c_2 = (r - r_0)^2$? Then $r_1 = r_2 = r_0$, and the "general solution" $\alpha r_0^n + \beta r_0^n = (\alpha + \beta) r_0^n$ collapses to a single constant times $r_0^n$ — only one free parameter, but we need two to match two initial conditions. The geometric guess gave us only one building block; we need a second.

💡 Intuition: where the missing solution comes from. When the two roots collide, the second independent solution is not another geometric sequence — it is $n \cdot r_0^{\,n}$. The factor of $n$ is exactly what is needed to break the tie. (The same phenomenon appears in repeated roots of linear differential equations, where the second solution is $x e^{rx}$.) You can verify directly that $n r_0^n$ satisfies the recurrence when $r_0$ is a double root; we do so in the proof.

Theorem (repeated root). If the characteristic equation has a single repeated root $r_0$ (so $r^2 - c_1 r - c_2 = (r - r_0)^2$, with $r_0 \ne 0$), the solutions of $a_n = c_1 a_{n-1} + c_2 a_{n-2}$ are exactly $$a_n = (\alpha + \beta n)\, r_0^{\,n}.$$

The strategy before the proof. It suffices to show $n r_0^n$ is a solution (we already know $r_0^n$ is); then any combination $(\alpha + \beta n) r_0^n$ is a solution by superposition, and the two-parameter family can match any two initial conditions. The key algebraic fact we'll use: a double root of $r^2 - c_1 r - c_2$ means both the equation and its derivative vanish at $r_0$, i.e. $r_0^2 = c_1 r_0 + c_2$ and $2 r_0 = c_1$.

Proof. Since $r_0$ is a double root, $r^2 - c_1 r - c_2 = (r - r_0)^2 = r^2 - 2r_0 r + r_0^2$. Matching coefficients, $c_1 = 2r_0$ and $c_2 = -r_0^2$. We claim $b_n = n r_0^n$ satisfies $b_n = c_1 b_{n-1} + c_2 b_{n-2}$. Compute the right-hand side: $$c_1 b_{n-1} + c_2 b_{n-2} = 2r_0 \cdot (n-1) r_0^{\,n-1} + (-r_0^2)\cdot (n-2) r_0^{\,n-2}.$$ Factor out $r_0^n$: $$= r_0^{\,n}\big[\,2(n-1) - (n-2)\,\big] = r_0^{\,n}\big[\,2n - 2 - n + 2\,\big] = r_0^{\,n}\cdot n = n r_0^{\,n} = b_n.$$ So $n r_0^n$ is a solution. Together with $r_0^n$, superposition gives that every $(\alpha + \beta n) r_0^n$ is a solution; matching $a_0 = \alpha$ and $a_1 = (\alpha + \beta) r_0$ determines $\alpha, \beta$ uniquely (the latter solvable for $\beta$ since $r_0 \ne 0$). $\blacksquare$

Worked example. Solve $a_n = 4a_{n-1} - 4a_{n-2}$ with $a_0 = 1$, $a_1 = 3$.

1. Characteristic equation: $r^2 - 4r + 4 = 0$.
2. Roots: $(r-2)^2 = 0$, so $r_0 = 2$, a double root.
3. General solution: $a_n = (\alpha + \beta n)\,2^n$.
4. Initial conditions: $n=0$ gives $\alpha = 1$; $n=1$ gives $(\alpha + \beta)\cdot 2 = 3$, so $\alpha + \beta = 3/2$, hence $\beta = 1/2$.
5. Closed form: $a_n = \left(1 + \tfrac{1}{2}n\right) 2^n = 2^n + n\,2^{n-1}$.

Check: $a_2$ from the formula is $(1 + 1)\cdot 4 = 8$; recurrence gives $4(3) - 4(1) = 8$. ✅ And $a_3$: formula $(1 + 3/2)\cdot 8 = 20$; recurrence $4(8) - 4(3) = 20$. ✅

The general recipe (order $k$). Form the characteristic equation $r^k - c_1 r^{k-1} - \cdots - c_k = 0$. For each root $r$ of multiplicity $m$, contribute the $m$ basic solutions $r^n, n r^n, n^2 r^n, \dots, n^{m-1} r^n$. The general solution is the linear combination of all basic solutions across all roots; fit the $k$ coefficients with the $k$ initial conditions.

🔄 Check Your Understanding 1. The Fibonacci recurrence $F_n = F_{n-1} + F_{n-2}$ has characteristic equation $r^2 - r - 1 = 0$. Are its roots distinct or repeated? (You don't need to compute them — use the discriminant.) 2. A recurrence has characteristic equation $(r-3)^2(r+1) = 0$. Write the form of its general solution (with unknown constants), before any initial conditions.

Answers

1. Distinct. The discriminant of $r^2 - r - 1$ is $(-1)^2 - 4(1)(-1) = 1 + 4 = 5 > 0$, so there are two distinct real roots (they are $\frac{1 \pm \sqrt 5}{2}$ — the golden ratio and its conjugate, which Chapter 19 uses for the closed form). 2. Root 3 has multiplicity 2 (contributes $3^n$ and $n 3^n$); root $-1$ has multiplicity 1 (contributes $(-1)^n$). So $a_n = (\alpha + \beta n)3^n + \gamma(-1)^n$.

18.5 Nonhomogeneous recurrences (an introduction)

The Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$ is not homogeneous — that stubborn "$+1$" is a standalone term. Recurrences of the form

$$a_n = c_1 a_{n-1} + \cdots + c_k a_{n-k} + f(n),$$

with a nonzero "forcing term" $f(n)$ that depends only on $n$, are nonhomogeneous. They appear constantly: counting problems with a fixed cost added at each level, and (in Chapter 19) the running time of recursive algorithms, where $f(n)$ is the work done outside the recursive calls.

There is a beautifully simple structure to their solutions, and it is worth stating as the organizing principle even though we only develop the easiest case.

The structure theorem (stated). Every solution of a nonhomogeneous linear recurrence has the form $$a_n = a_n^{(h)} + a_n^{(p)},$$ where $a_n^{(p)}$ is any one particular solution of the full nonhomogeneous recurrence, and $a_n^{(h)}$ is the general solution of the associated homogeneous recurrence (the same recurrence with $f(n)$ deleted). The homogeneous part supplies the free constants you fit to the initial conditions; the particular part absorbs the forcing term.

💡 Intuition: why solutions split this way. Suppose $a_n$ and $a_n^{(p)}$ both satisfy the full nonhomogeneous recurrence. Subtract the two equations: the $f(n)$ on each side cancels, so the difference $a_n - a_n^{(p)}$ satisfies the homogeneous recurrence. Hence $a_n = a_n^{(p)} + (\text{something homogeneous})$. The two pieces are exactly the "respond to the forcing" part and the "free to match initial conditions" part.

The practical method: guess a particular solution shaped like $f(n)$, with undetermined coefficients, and solve for those coefficients by substitution. A short table of good first guesses:

⚠️ Common Pitfall: when the guess clashes with the homogeneous solution. If your trial particular solution is already a solution of the homogeneous recurrence (for instance $f(n) = C \cdot s^n$ when $s$ happens to be a characteristic root), the naive guess collapses to 0 and fails. The fix mirrors the repeated-root case: multiply the trial by $n$ (or $n^2$, etc.) until it is no longer a homogeneous solution. We flag this; the full treatment is Chapter 19's territory.

Worked example: solving the Tower of Hanoi. Solve $H_n = 2H_{n-1} + 1$, $H_0 = 0$.

The strategy first. The associated homogeneous recurrence is $H_n = 2H_{n-1}$, whose characteristic root is 2, giving $H_n^{(h)} = \alpha\, 2^n$. The forcing term is the constant 1, so we try a constant particular solution $H_n^{(p)} = A$. Add the pieces, then fit $\alpha$ to $H_0 = 0$.

Solution.

1. Particular solution. Guess $H_n^{(p)} = A$ (a constant). Substituting into the full recurrence: $A = 2A + 1$, so $-A = 1$, giving $A = -1$. Thus $H_n^{(p)} = -1$.
2. Homogeneous solution. $H_n = 2H_{n-1}$ has root 2, so $H_n^{(h)} = \alpha\, 2^n$.
3. Combine: $H_n = \alpha\, 2^n - 1$.
4. Initial condition. $H_0 = 0$ gives $\alpha \cdot 1 - 1 = 0$, so $\alpha = 1$.
5. Closed form: $H_n = 2^n - 1$.

This confirms the pattern $1, 3, 7, 15, \dots$ we guessed in 18.2 — but now it's derived. The minimum number of moves to solve the Tower of Hanoi with $n$ disks is exactly $2^n - 1$.

def hanoi_closed(n):
    return 2**n - 1

def hanoi_rec(n):
    if n == 0: return 0
    return 2 * hanoi_rec(n - 1) + 1

print([hanoi_closed(n) for n in range(7)])
print([hanoi_rec(n)    for n in range(7)])
# Expected output:
# [0, 1, 3, 7, 15, 31, 63]
# [0, 1, 3, 7, 15, 31, 63]

🔄 Check Your Understanding 1. For the recurrence $a_n = 3a_{n-1} + 4$ (forcing term the constant 4), what form would you guess for a particular solution, and what equation determines its coefficient? 2. Why does the "$+1$" in the Hanoi recurrence make the growth of $H_n$ no slower than $2^n$ — i.e., why couldn't the answer have turned out to be, say, $n^2$?

Answers

1. Guess a constant $a_n^{(p)} = A$; substituting gives $A = 3A + 4$, so $A = -2$. (The homogeneous part is $\alpha 3^n$, giving $a_n = \alpha 3^n - 2$.) 2. The homogeneous part $\alpha 2^n$ dominates: the recurrence at least doubles the previous value each step (the $+1$ only adds more), so $H_n$ grows exponentially. A polynomial like $n^2$ can't satisfy $H_n = 2H_{n-1} + 1$ because doubling forces exponential growth — this is the "linear recurrence, exponential growth" point from 18.3.

18.6 From recursive code to recurrence

We opened with the claim that every recursive function hides an equation. Here we make extracting that equation a routine, because it is the entry point to all algorithm analysis: you cannot bound a recursive algorithm's running time until you have written down — and solved — its recurrence.

The recipe has two questions:

1. How does the input shrink, and into how many pieces? Each recursive call on a smaller input becomes a term on the right-hand side.
2. How much work happens in this call, outside the recursive calls? That becomes the forcing term $f(n)$ (often a constant, or $O(n)$).

Let $T(n)$ denote the running time (count of basic operations) on an input of size $n$.

Example A: a linear recursion. Summing a list by peeling off the head:

def list_sum(xs):
    if not xs:          # base case: O(1)
        return 0
    return xs[0] + list_sum(xs[1:])   # one call on size n-1

One recursive call on an input one smaller, plus a constant amount of work (an addition and an index) in this call. So $T(n) = T(n-1) + c$ with $T(0) = c_0$. This is a nonhomogeneous recurrence with a constant forcing term; unrolling (or the method of 18.5) gives $T(n) = c_0 + cn = O(n)$. The function is linear-time — as you'd hope for adding up $n$ numbers. (In real Python, xs[1:] itself copies the list and costs $O(n)$, which would change the analysis; we are counting the algorithm's own arithmetic, not the slicing — a worthwhile thing to notice and a reason to prefer an index parameter.)

Example B: halving the input. Binary search:

def bsearch(xs, target, lo, hi):
    if lo > hi:                 # base case
        return -1
    mid = (lo + hi) // 2
    if xs[mid] == target:
        return mid
    if xs[mid] < target:
        return bsearch(xs, target, mid + 1, hi)   # one call, half the range
    return bsearch(xs, target, lo, mid - 1)       # one call, half the range

Each call does a constant amount of work and then recurses on (at most) half the remaining range. So $T(n) = T(n/2) + c$. This is a divide-and-conquer recurrence — the input shrinks by a factor, not by a constant. We will solve this exact recurrence with the Master Theorem in Chapter 19; the answer is $T(n) = O(\log n)$, the reason binary search is fast.

Example C: two calls — the cost of naive Fibonacci. Now the function from page one:

def fib(n):
    if n < 2:                       # O(1)
        return n
    return fib(n - 1) + fib(n - 2)  # TWO calls

The running time satisfies its own recurrence, distinct from the value it computes: $$T(n) = T(n-1) + T(n-2) + c.$$ That's the Fibonacci recurrence (plus a constant) — so the time to compute $F_n$ naively grows like $F_n$ itself, which is exponential ($\approx \phi^n$, with $\phi$ the golden ratio of Chapter 19). This is why naive Fibonacci is unusably slow: the recurrence for its cost is the very sequence it's computing. Recognizing that from the code — two recursive calls, each on a nearly-full-size input — tells you the algorithm is exponential before you ever run it.

🚪 Threshold Concept: the recurrence is the algorithm's cost, made visible. Once you can look at recursive code and immediately write its recurrence, the asymptotic cost stops being a mystery you measure with a stopwatch and becomes something you derive. "One call on $n-1$, constant work" is linear. "One call on $n/2$, constant work" is logarithmic. "Two calls on $n/2$, linear work" (merge sort, next chapter) is $n \log n$. "Two calls on nearly $n$" is exponential. This single reflex — code to recurrence to growth rate — is the backbone of algorithm analysis and the bridge into Chapter 19.

🔄 Check Your Understanding 1. A function makes one recursive call on input size $n-1$ and does $O(n)$ work in the current call (say, a linear scan before recursing). Write its time recurrence. Is the total quadratic or linear? 2. Contrast the recurrence for the value $F_n = F_{n-1} + F_{n-2}$ with the recurrence for the time $T(n) = T(n-1) + T(n-2) + c$ of computing it naively. Why do they have the same shape, and what does that tell you about the running time?

Answers

1. $T(n) = T(n-1) + cn$. Unrolling sums $c(n + (n-1) + \cdots + 1) = c\,\frac{n(n+1)}{2} = O(n^2)$ — quadratic (this is the cost shape of, e.g., selection sort). 2. Both are second-order with the same "previous two terms" structure, because the function makes one call on $n-1$ and one on $n-2$; the time to handle each subproblem is itself $T$ of that smaller size. Same recurrence ⇒ same growth: the running time grows like $F_n \approx \phi^n$, i.e. exponentially. Memoizing collapses the two calls' overlap and makes it linear — a payoff you'll appreciate in Chapter 19.

Project Checkpoint: a general linear-recurrence solver for the Toolkit

In Chapter 6 you started dmtoolkit/recurrences.py with check_identity and a naive fib. Now we add the function the module is named for: a numerical solver that, given the coefficients of a linear recurrence and its initial conditions, computes the $n$-th term by faithfully unrolling the recurrence. This is the canonical solve_linear(coeffs, inits, n) from the Toolkit API (_style-bible.md §4).

The contract: coeffs = [c1, c2, ..., ck] are the coefficients in $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \cdots + c_k a_{n-k}$, and inits = [a0, a1, ..., a_{k-1}] are the $k$ initial conditions. The function returns $a_n$.

def solve_linear(coeffs, inits, n):
    """nth term of a linear recurrence a_n = c1*a_{n-1} + ... + ck*a_{n-k}.
    coeffs = [c1,...,ck] (c1 multiplies the most recent term);
    inits  = [a0,...,a_{k-1}] (k initial conditions). Iterative, O(n*k)."""
    k = len(coeffs)
    if n < k:
        return inits[n]                 # answer is an initial condition
    a = list(inits)                     # sliding window of the last k terms
    for _ in range(k, n + 1):
        # most recent term is a[-1]; coeffs[0] multiplies it
        nxt = sum(coeffs[i] * a[-1 - i] for i in range(k))
        a.append(nxt)
        a.pop(0)                        # keep only the last k
    return a[-1]

# Fibonacci: a_n = 1*a_{n-1} + 1*a_{n-2}, inits a0=0, a1=1
print(solve_linear([1, 1], [0, 1], 10))
# The 5*a_{n-1} - 6*a_{n-2} example from 18.4, inits a0=1, a1=4
print(solve_linear([5, -6], [1, 4], 5))
# Expected output:
# 55
# 454

We hand-traced both: Fibonacci gives $F_{10} = 55$ (counting $F_0 = 0$), and the second is the $a_5 = 454$ we verified by closed form in 18.4. Note what this solver does and doesn't do — it unrolls the recurrence in $O(nk)$ time, which is honest and general but not clever. Chapter 19 adds the matrix-exponentiation fib(n) that computes Fibonacci in $O(\log n)$ by squaring a $2 \times 2$ matrix, and the closed-form solver that uses the characteristic roots from this chapter. The capstone's RSA and graph tracks don't need recurrences directly, but solve_linear is the engine behind every "how many?" and "how long?" answer your Toolkit can now give — and the bridge to the efficient solvers of the next chapter.

Toolkit so far: logic.py (Ch. 1–3), sets.py (Ch. 8), relations.py (Ch. 12–13), combinatorics.py (Ch. 15–17), and now recurrences.py gains solve_linear. Chapter 19 completes the module with the fast fib.

Summary

A recurrence relation defines $a_n$ in terms of earlier terms; with enough initial conditions it specifies a unique sequence. Solving a recurrence means converting it into a closed form you can evaluate and analyze directly.

Classification (do this first — it picks your tool):

The characteristic-equation method (linear, homogeneous, constant coefficients):

• Distinct roots $r_1 \ne r_2$: $a_n = \alpha r_1^n + \beta r_2^n$.
• Repeated root $r_0$: $a_n = (\alpha + \beta n) r_0^n$ — the extra factor of $n$ supplies the second building block.

Nonhomogeneous $a_n = (\text{linear part}) + f(n)$: solution is $a_n = a_n^{(h)} + a_n^{(p)}$, the homogeneous general solution plus any particular solution (guess one shaped like $f(n)$; multiply by $n$ if it clashes with a homogeneous solution). Fit constants to the initial conditions last, after adding the particular solution.

Key results derived this chapter:

Code → recurrence (the analysis reflex):

Toolkit addition: solve_linear(coeffs, inits, n) — unrolls any linear recurrence in $O(nk)$.

Spaced Review

Retrieval keeps knowledge available. Answer from memory before checking.

1. (Ch. 11) Distinguish a closed-form (explicit) description of a sequence from a recursive one, and give one advantage of each. Which one is a recurrence relation?
2. (Ch. 11) The Tower of Hanoi solution $H_n = 2^n - 1$ can be reached without the characteristic equation, by unrolling: $H_n = 2H_{n-1}+1 = 2(2H_{n-2}+1)+1 = \cdots$. Carry the unrolling far enough to recognize a geometric series, and evaluate it (you may use the closed form for $1 + 2 + 4 + \cdots + 2^{n-1}$ from Chapter 11).
3. (Ch. 7) We set up the $2 \times n$ tiling recurrence by case analysis on the first column. Why is strong induction (Chapter 7) the right tool to prove a closed-form claim about a second-order recurrence like this, rather than ordinary induction?
4. (Ch. 7) A recurrence with two initial conditions is a recursive definition in the sense of Chapter 7. What are the "base cases" of the Fibonacci recursive definition, and why does a second-order recurrence need two of them?

Answers

1. A closed form computes $a_n$ directly from $n$ (advantage: $O(1)$ evaluation, easy growth comparison); a recursive description computes $a_n$ from earlier terms (advantage: usually far easier to derive from a problem's structure). The recurrence relation is the recursive description.
2. $H_n = 2H_{n-1}+1 = 2^2 H_{n-2} + 2 + 1 = 2^3 H_{n-3} + 4 + 2 + 1 = \cdots = 2^n H_0 + (2^{n-1} + \cdots + 2 + 1)$. Since $H_0 = 0$, this is the geometric sum $\sum_{i=0}^{n-1} 2^i = 2^n - 1$ (the Chapter 11 closed form for a geometric series with ratio 2). 3. To prove a claim about $a_n$ for a second-order recurrence, the inductive step needs both $a_{n-1}$ and $a_{n-2}$ — i.e., you must assume the result for two previous cases at once, which is exactly what strong induction grants (ordinary induction gives you only the single previous case). 4. The base cases are $F_0 = 0$ and $F_1 = 1$. A second-order recurrence computes each new term from the two before it, so it cannot get started until two terms are given outright; one base case would leave $F_2 = F_1 + F_0$ underdetermined.

What's Next

You can now set up a recurrence from a problem and solve the linear constant-coefficient family by hand. Two big pieces remain. First, the recurrences that govern divide-and-conquer algorithms — $T(n) = aT(n/b) + f(n)$, where the input shrinks by a factor — don't fit the characteristic-equation mold; Chapter 19 solves them with the recursion-tree method and the Master Theorem, and uses them to prove that merge sort is $O(n \log n)$ and binary search is $O(\log n)$. Second, we still owe Fibonacci its closed form: Chapter 19 cracks the characteristic equation $r^2 - r - 1 = 0$ to reveal the golden ratio $\phi = \frac{1+\sqrt5}{2}$ and the formula $F_n = \frac{1}{\sqrt5}(\phi^n - \psi^n)$ — and then shows how to compute $F_n$ in $O(\log n)$ time by matrix exponentiation. The characteristic equation you learned to write in this chapter is the key that unlocks both.