Exercises: Recurrence Relations

These build from mechanical warm-ups to modeling, code, and the structural theory behind the characteristic-equation method. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; set up each one yourself before you peek. Throughout, "solve a recurrence" means find a closed form and verify it against the initial conditions (§18.4), and "set up a recurrence" means write the relation plus enough initial conditions to pin down one sequence (§18.1).

Part A — Warm-ups (⭐)

18.1 † For the recurrence $a_n = 3a_{n-1} - 2a_{n-2}$ with $a_0 = 1$, $a_1 = 3$, compute $a_2$, $a_3$, and $a_4$ by unrolling. (Do not look for a closed form yet — just turn the crank.)

18.2 State the order of each recurrence and say how many initial conditions it needs: (a) $a_n = 7a_{n-1}$; (b) $a_n = a_{n-1} + a_{n-3}$; (c) $a_n = 2a_{n-2} - a_{n-5}$; (d) $a_n = a_{n-1} + a_{n-2} + 1$.

18.3 † Classify each recurrence as linear or nonlinear, homogeneous or nonhomogeneous, and constant- or variable-coefficient, then give a one-word verdict on whether the characteristic-equation method of §18.4 applies directly: (a) $a_n = 4a_{n-1} - 4a_{n-2}$; (b) $a_n = 2a_{n-1} + 3^n$; (c) $a_n = a_{n-1}a_{n-2}$; (d) $a_n = (n-1)a_{n-1}$; (e) $a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}$.

18.4 Write the characteristic equation for each linear homogeneous recurrence (do not solve it): (a) $a_n = 5a_{n-1} - 6a_{n-2}$; (b) $a_n = a_{n-2}$; (c) $a_n = 2a_{n-1} + a_{n-2} - 2a_{n-3}$.

18.5 † A sequence is given by the closed form $a_n = 4 \cdot 2^n + (-1)^n$. Compute $a_0, a_1, a_2$, then verify that the sequence satisfies the recurrence $a_n = a_{n-1} + 2a_{n-2}$. (This previews the two-way check we use constantly: a closed form must agree with the recurrence at every step.)

18.6 For the Tower of Hanoi recurrence $H_n = 2H_{n-1} + 1$ with $H_0 = 0$, identify which term is the forcing term $f(n)$ and which part is the associated homogeneous recurrence (§18.5).

Part B — Prove it (⭐⭐)

18.7 † (Scaffolded — fill in the missing steps.) Solve $a_n = 6a_{n-1} - 8a_{n-2}$ with $a_0 = 3$, $a_1 = 10$. Complete each blank. - Characteristic equation: from $a_n = 6a_{n-1} - 8a_{n-2}$ we read $c_1 = 6$, $c_2 = -8$, giving $r^2 - 6r - (\underline{\hphantom{xx}}) = r^2 - 6r + 8 = 0$. - Roots: $r^2 - 6r + 8 = (r-2)(r-\underline{\hphantom{xx}})$, so $r_1 = 2$, $r_2 = \underline{\hphantom{xx}}$ — distinct. - General solution: $a_n = \alpha\, 2^n + \beta\, \underline{\hphantom{xxxx}}$. - Initial conditions: $n=0$ gives $\alpha + \beta = \underline{\hphantom{xx}}$; $n=1$ gives $2\alpha + 4\beta = \underline{\hphantom{xx}}$. Solving, $\beta = \underline{\hphantom{xx}}$ and $\alpha = \underline{\hphantom{xx}}$. - Closed form: $a_n = \underline{\hphantom{xxxxxxxx}}$. Verify it gives $a_2 = 36$ against the recurrence.

18.8 Solve the repeated-root recurrence $a_n = 6a_{n-1} - 9a_{n-2}$ with $a_0 = 2$, $a_1 = 9$. Show the characteristic equation, identify the double root, write the general solution in the form $(\alpha + \beta n) r_0^n$, fit the constants, and check your formula against $a_2$ computed from the recurrence.

18.9 † Prove the superposition property that makes the whole method work (§18.3): if the sequences $\{x_n\}$ and $\{y_n\}$ each satisfy the linear homogeneous recurrence $a_n = c_1 a_{n-1} + c_2 a_{n-2}$, then for any constants $\alpha, \beta$ the sequence $z_n = \alpha x_n + \beta y_n$ also satisfies it. (Substitute $z_n$ into the right-hand side and use the two hypotheses.)

18.10 Solve the third-order recurrence $a_n = 6a_{n-1} - 11a_{n-2} + 6a_{n-3}$ with $a_0 = 0$, $a_1 = 1$, $a_2 = 5$. (Hint: the characteristic equation $r^3 - 6r^2 + 11r - 6 = 0$ has three small integer roots; test $r = 1, 2, 3$.)

18.11 † Verify directly, without using the repeated-root theorem, that $b_n = n \cdot 3^n$ is a solution of $a_n = 6a_{n-1} - 9a_{n-2}$ (the recurrence of 18.8). That is, substitute $b_{n-1}$ and $b_{n-2}$ into $6a_{n-1} - 9a_{n-2}$ and simplify to $n \cdot 3^n$. Explain why this confirms the "extra factor of $n$" rule for a double root $r_0 = 3$.

18.12 Solve the nonhomogeneous recurrence $a_n = 3a_{n-1} + 4$ with $a_0 = 1$ (§18.5). Find a constant particular solution, add the homogeneous solution, then fit the constant to $a_0$. Verify $a_2 = 25$.

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Keep each function under ~30 lines.

18.13 † Write a function tilings(n) that returns the number of ways to tile a $2 \times n$ board with dominoes, computed straight from the recurrence $t_n = t_{n-1} + t_{n-2}$ with $t_1 = 1$, $t_2 = 2$ (§18.2). Print [tilings(n) for n in range(1, 9)] and give the expected output. What familiar sequence appears?

18.14 Use the Toolkit's solve_linear(coeffs, inits, n) from this chapter's Project Checkpoint to compute the 20th binary-string count $s_{20}$ for strings with no two consecutive zeros, given $s_n = s_{n-1} + s_{n-2}$, $s_1 = 2$, $s_2 = 3$. Write the three lines of code (set up coeffs, inits, and the call) and state what value you expect. (Careful: solve_linear indexes its inits as $a_0, a_1, \dots$ — decide what to use for the zeroth term so that the call returns $s_{20}$.)

18.15 † Write an iterative (loop, not recursion) function hanoi(n) returning the minimum number of moves for the Tower of Hanoi, computed from $H_n = 2H_{n-1} + 1$, $H_0 = 0$. Then write a one-line hanoi_closed(n) using the closed form derived in §18.5. Print both for $n = 0, \dots, 6$ and confirm they agree.

18.16 Write a function count_calls(n) that returns the number of calls the naive fib from the Overview makes to compute fib(n) (count every invocation, including the top one). Set up the recurrence the call-count satisfies, implement it iteratively, and print count_calls(10) with the expected value. (Hint: a call on n >= 2 is one call plus all the calls of fib(n-1) and fib(n-2); for n < 2 it is a single call.)

Part D — Find the error (⭐⭐)

Each item below contains a flawed derivation. State precisely which step fails and why, then give the correct result.

18.17 † Claim: the recurrence $a_n = 4a_{n-1} - 4a_{n-2}$ has general solution $a_n = \alpha\, 2^n + \beta\, 2^n$. "Derivation": the characteristic equation is $r^2 - 4r + 4 = 0$ with roots $r_1 = 2$ and $r_2 = 2$, so by the distinct-roots theorem the general solution is $\alpha\, 2^n + \beta\, 2^n$. — Find the flaw, and write the correct general solution.

18.18 Claim: $H_n = 2H_{n-1} + 1$ with $H_0 = 0$ has solution $H_n = \alpha\, 2^n$ because its characteristic root is 2. "Derivation": the recurrence is linear with characteristic equation $r - 2 = 0$, root 2, so $H_n = \alpha\, 2^n$; using $H_0 = 0$ gives $\alpha = 0$, hence $H_n = 0$ for all $n$. — Two things are wrong here. Identify both, and state the correct closed form.

18.19 † Claim: to solve $a_n = 5a_{n-1} - 6a_{n-2}$ with $a_0 = 1$, $a_1 = 4$, a student writes $a_n = \alpha\, 2^n + \beta\, 3^n$, then "to save time" fits the constants using $a_1$ and $a_2$ instead of $a_0$ and $a_1$, getting a different $\alpha, \beta$. They claim it doesn't matter which two terms you use. "Derivation": uses $a_1 = 4$ and the recurrence-computed $a_2 = 14$. — Is the student's reasoning sound? Explain what would go wrong if they had used $a_0$ and $a_2$ (two terms that skip $a_1$), and connect this to why exactly $k$ consecutive initial conditions are needed.

18.20 Claim: the nonhomogeneous recurrence $a_n = 2a_{n-1} + 3$ with $a_0 = 1$ has closed form $a_n = 2^n - 3$. "Derivation": the particular solution $A$ satisfies $A = 2A + 3$, so $A = -3$; the homogeneous part is $\alpha\, 2^n$. The student then fits $\alpha$ to the initial condition using the homogeneous part alone — "$\alpha\, 2^0 = a_0$, so $\alpha = 1$" — and reports $a_n = \alpha\, 2^n + A = 2^n - 3$. — The particular solution and homogeneous form are both correct, but the constant was fit at the wrong moment. Name the error precisely (relate it to the §18.5 rule "fit the constants last, after adding the particular solution"), and give the correct closed form. (Check it against $a_1$ computed from the recurrence.)

Part E — Model it & Conjecture and test (⭐⭐⭐)

18.21 † (Model it.) A vending machine accepts \$1 coins and \$2 coins. In how many ordered ways (the sequence of coins matters) can you insert exactly $n$ dollars? Set up a recurrence by conditioning on the last coin inserted (the "condition on the last choice" move from §18.2), give the initial conditions, and identify which famous sequence you get. You do not need a closed form.

18.22 (Model it.) A simple model of a rabbit colony: each month, every pair of adult rabbits produces one new pair, and a newborn pair takes one month to become adult (and never dies). Let $R_n$ be the number of pairs in month $n$. By splitting month $n$'s pairs into "adults last month" and "newborns this month," set up a recurrence for $R_n$ and state the initial conditions. Which anchor sequence of this book appears, and why is this historically the original appearance (§18.2)?

18.23 † (Conjecture and test, then prove.) Define $a_0 = 0$ and $a_n = 2a_{n-1} + 1$ for $n \ge 1$ (the Hanoi recurrence). Use solve_linear (or a short loop) to print $a_0, \dots, a_8$, conjecture a closed form, then prove it by the method of §18.5 (particular + homogeneous). State what the computed values gave you as evidence and why evidence alone is not a proof (theme four).

18.24 (Conjecture and test.) For the Fibonacci numbers $F_n$ ($F_0 = 0, F_1 = 1$), the ratio $F_{n+1}/F_n$ seems to approach a fixed limit. Write code that prints $F_{n+1}/F_n$ for $n = 1, \dots, 12$ (use solve_linear or a loop). Conjecture the limit to three decimal places. Then, without solving the recurrence, argue that if the ratio approaches some limit $L$, then $L$ must satisfy $L = 1 + 1/L$ — i.e. $L^2 - L - 1 = 0$, the characteristic equation of §18.4. (Chapter 19 turns this into the golden-ratio closed form.)

18.25 † (Model it — from code.) You are handed this function and asked for its asymptotic running time before anyone runs it:

def mystery(n):
    if n <= 1:
        return 1
    total = 0
    for i in range(n):        # a linear scan
        total += i
    return total + mystery(n - 1)

Following the recipe of §18.6, write the recurrence $T(n)$ for its running time (one recursive call on $n-1$, plus the work of the loop), then unroll it to a closed form and state the growth rate using $O(\cdot)$ notation. Which row of the §18.6 "code → recurrence" table does this match?

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

18.26 † (Ch. 7 + 18.) We set up the $2 \times n$ tiling recurrence $t_n = t_{n-1} + t_{n-2}$ in §18.2 and will get its closed form in Chapter 19. Suppose someone hands you the conjecture $t_n = F_{n+1}$ (Fibonacci, shifted). Explain why strong induction (Chapter 7), not ordinary induction, is the right tool to prove it, and state the two base cases the proof would need. (You need not write the full proof — just the structure and why a second-order recurrence forces it.)

18.27 (Ch. 11 + 18.) Unroll the Hanoi recurrence $H_n = 2H_{n-1} + 1$ (with $H_0 = 0$) by hand: $H_n = 2(2H_{n-2}+1)+1 = \cdots$. Carry it far enough to see a geometric series, then evaluate that series using the Chapter 11 closed form for $\sum_{i=0}^{n-1} 2^i$. Confirm you recover $H_n = 2^n - 1$. What is the advantage of the characteristic/particular method of §18.5 over this unrolling for a harder forcing term?

18.28 † (Ch. 15 + 18.) The tiling and binary-string setups in §18.2 both ended with the sum rule of Chapter 15 ("split into mutually exclusive, exhaustive cases and add"). For the binary strings of length $n$ with no two consecutive zeros, write the one sentence that invokes the sum rule and explain why the two cases (ends in 1, ends in 0) are genuinely disjoint and exhaustive — the two conditions the sum rule requires.

18.29 (Ch. 1/2 + 18.) Let $P(n)$ be the predicate "$a_n = 2^n - 1$" for the Hanoi sequence. Using quantifier notation from Chapters 1–2, write the full statement we ultimately prove, including the domain of $n$. Then write the recurrence-plus-initial-condition specification of the same sequence as a conjunction of two statements (one universally quantified, one a single equation), and explain why both halves are needed to determine the sequence (§18.1).

18.30 (Deep Dive.) Prove the uniqueness half of the distinct-roots theorem (§18.4): given a second-order linear homogeneous recurrence with distinct characteristic roots $r_1 \ne r_2$, show that for any prescribed $a_0$ and $a_1$ there is exactly one choice of constants $\alpha, \beta$ with $a_n = \alpha r_1^n + \beta r_2^n$. (Set up the $2 \times 2$ linear system in $\alpha, \beta$ and show its determinant is $r_2 - r_1 \ne 0$, so the solution is unique.)

18.31 (Deep Dive.) Building on the superposition property (18.9) and the matching argument (18.30), assemble the full statement that "$\alpha r_1^n + \beta r_2^n$ describes every solution of the distinct-root second-order recurrence." Outline the two parts: (i) every such combination is a solution; (ii) every solution is such a combination — using uniqueness of a sequence given its first two terms (§18.1) to argue (ii). This is the claim the chapter's Deep Dive learning path asked you to nail down.

18.32 (Deep Dive — repeated roots.) Generalize 18.11: prove that whenever $r_0$ is a double root of $r^2 - c_1 r - c_2 = 0$, the sequence $n r_0^n$ satisfies $a_n = c_1 a_{n-1} + c_2 a_{n-2}$. Use the two facts a double root gives you — $r_0^2 = c_1 r_0 + c_2$ and $2r_0 = c_1$ — exactly as in the §18.4 proof, but keep $c_1, c_2$ symbolic.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each "solve a recurrence," the rubric rewards: the correct classification, a correct characteristic equation, roots with their multiplicities, the right form of the general solution, constants fit from the stated initial conditions, and an independent check against one more term.