Further Reading: Recurrence Relations

Annotated pointers for going deeper. Start with the textbook sections that mirror this chapter, then branch toward whichever pulls you: the combinatorial side (counting with recurrences), the algorithms side (recurrences as running-time tools — the Chapter 19 direction), or the closed-form theory. All sources below are Tier 1 (canonical, verified) or Tier 2 (a real, attributable idea whose exact details you should confirm yourself).

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §8.1–8.2 The market-standard treatment of recurrence relations: §8.1 sets up recurrences as models (Hanoi, tilings, string counts — the same examples as this chapter), and §8.2 develops the characteristic-equation method for linear homogeneous and nonhomogeneous recurrences with constant coefficients, including the repeated-root case. If you want a larger graded exercise bank than this chapter provides, this is the first stop.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the recurrences chapter Freely available. The most CS-flavored presentation in print: recurrences are introduced as the cost of recursive programs (the §18.6 spirit) and solved both by unrolling ("plug and chug") and by the characteristic-equation method, with the Tower of Hanoi as the running example. The natural companion to this chapter's "code → recurrence" thread.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 1 (and §1.1 on Hanoi) The deepest treatment of setting up and solving recurrences as a craft. Chapter 1 opens with the Tower of Hanoi and the "repertoire method" for guessing closed forms; later chapters develop generating functions, a more powerful solving technique you will appreciate once the characteristic equation feels routine. Denser than the others, but it rewards the effort.

Recurrences as running-time tools (the Chapter 19 direction)

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 4 The canonical reference for solving the divide-and-conquer recurrences this chapter deliberately left to Chapter 19 — $T(n) = aT(n/b) + f(n)$ — via the recursion-tree method and the Master Theorem. Read §4.3–§4.5 right before (or alongside) Chapter 19. CLRS §2.3 also derives the merge-sort recurrence the §18.6 table previews.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the "Recurrence Relations" section Freely available. A gentle, example-first treatment with the "telescoping / iterate-then-guess" approach to solving recurrences foregrounded, plus the characteristic-root method. A good second-explanation if §18.4 went by too fast, and the price is right.

On the Tower of Hanoi and Fibonacci specifically

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §1.2.8 (Fibonacci numbers) The definitive reference on Fibonacci identities, their recurrence, and the history. Many of the identities here are the "conjecture and test, then prove" problems you could pose yourself; §1.2.8 also foreshadows the closed form Chapter 19 derives.

"Tower of Hanoi" and the "priests of Brahma" legend (Édouard Lucas, 1883) (Tier 2.) The puzzle and its end-of-the-world legend were popularized by the French mathematician Édouard Lucas (after whom the Lucas numbers are named). The framing is folklore, not history — confirm specifics before repeating them — but it is the origin of the $2^{64} - 1$ figure in §18.2 and a memorable hook for exponential growth.

Free online and video

The On-Line Encyclopedia of Integer Sequences (OEIS), oeis.org (Tier 2 — community-maintained.) Look up A000045 (Fibonacci), A000073 (Tribonacci, the §18.4 "three-step" recurrence), and A000225 ($2^n - 1$, the Tower of Hanoi counts). Each entry lists the recurrence, closed form, and dozens of identities — an excellent source of recurrences to set up and solve for practice. Verify any specific identity before relying on it.

3Blue1Brown, "Binary, Hanoi, and Sierpinski" (YouTube) (Tier 2 — free.) A visual tour connecting the Tower of Hanoi's recurrence to binary counting and to fractal structure. Excellent for the intuition behind why the Hanoi recurrence forces exponential growth, complementing the algebra of §18.5.

Suggested order

  1. Re-read §§18.2–18.4 here, then work Rosen §8.1–8.2 exercises for drill on the characteristic-equation method (distinct and repeated roots).
  2. Read the MIT 6.042 recurrences chapter for the "recurrence = cost of recursion" framing that powers §18.6.
  3. If the solving still feels mechanical-but-mysterious, read Levin's section and the 3Blue1Brown video for a second angle and the geometric picture.
  4. Save CLRS Chapter 4 for immediately before Chapter 19 — it is the divide-and-conquer sequel this chapter sets up.
  5. Browse Concrete Mathematics Ch. 1 and the OEIS entries when you want to go beyond the syllabus into generating functions and the wider world of recurrences.