Further Reading: Solving Recurrence Relations

Annotated pointers for going deeper on divide-and-conquer recurrences, the Master Theorem, and the fast Fibonacci algorithms. Start with the core textbook treatments, then branch toward whichever pulls you: the algorithmic side (recursion trees, the proof of the theorem), the "what to do when it fails" side (Akra–Bazzi, substitution), or the Fibonacci/golden-ratio thread.

Core textbook treatments

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Chapter 4 ("Divide- and-Conquer") The canonical reference for everything in this chapter: the substitution method, recursion trees, the Master Theorem (stated and proved), and the worked merge-sort recurrence. The 4th edition also presents the Akra–Bazzi method (§19.6's tool for unequal splits) carefully. If you read one thing after this chapter, read this — §4.3 (substitution), §4.4 (recursion trees), §4.5 (Master Theorem), §4.6 (proof).

Rosen, Discrete Mathematics and Its Applications (8th ed.), §8.1–8.3 Discrete-math-flavored treatment of recurrences: §8.1 sets them up (the Chapter 18 material), §8.3 covers divide-and-conquer recurrences and the Master Theorem in the style closest to this book's. A large, well-graded exercise bank if you want more drill than this chapter's set provides.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), the recurrences chapters Freely available. Develops linear and divide-and-conquer recurrences side by side, with the same "recurrences are how we analyze recursive algorithms" spirit as this chapter. The plug-and-chug, guess-and-verify, and Akra–Bazzi material is especially clear, and the merge-sort and Fibonacci examples run throughout — a perfect companion to §§19.4–19.5.

On the recursion tree and the Master Theorem's proof

CLRS (4th ed.), §4.4 and §4.6 §4.4 makes the recursion-tree method (§19.2) rigorous as a way to guess a bound; §4.6 turns the tree sum into the actual proof of the Master Theorem by evaluating the geometric series in all three regimes — exactly the Deep Dive this chapter sketches at the end of §19.3.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapters 1–2 and §7.3 For readers who want the manipulation behind solving recurrences — summation techniques, generating functions, and the repertoire method. Denser than CLRS, but it shows recurrence-solving as a craft. Save the generating-function material for after Chapter 18's sequences feel comfortable.

When the Master Theorem fails

Akra, M. & Bazzi, L., "On the solution of linear recurrence equations" (1998) Tier 2 — the original Akra–Bazzi paper. The generalization (§19.6) that handles unequal subproblem sizes such as $T(n) = T(n/3) + T(2n/3) + \Theta(n)$, which the Master Theorem cannot touch. For a gentler route, read the Akra–Bazzi section in CLRS or MIT 6.042 first; reach for the paper only if you want the source.

CLRS (4th ed.), §4.3 (the substitution method) The universal backstop when no closed theorem applies: guess the bound (often from a recursion tree), then prove it by induction (Chapter 6). The standard treatment of guessing the right form, handling the "lower-order term" subtlety, and verifying both upper and lower bounds — the technique behind this chapter's substitution exercises (19.15, 19.16, 19.33).

The Fibonacci / golden-ratio thread

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), §6.6 ("Fibonacci Numbers") The definitive mathematical treatment: Binet's closed form, the golden ratio, the matrix identity $M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}$ (§19.5), and a wealth of identities. Read this to see the matrix method and the closed form as two faces of the same structure.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §1.2.8 ("Fibonacci Numbers") A rigorous, historically rich account of Fibonacci numbers and their growth rate $\Theta(\phi^n)$ — the fact that explains why the naive recursion (§19.5) is exponential. Pairs well with the matrix-exponen- tiation algorithm as the "why so fast / why so slow" backdrop.

"Fibonacci numbers" — OEIS sequence A000045 (oeis.org) Free online. The Online Encyclopedia of Integer Sequences entry, with dozens of identities (including the fast-doubling identity $F_{2k} = F_k(2F_{k+1} - F_k)$ behind an alternative $O(\log n)$ algorithm) — a rich source of "conjecture and test, then prove" exercises like 19.29.

Connecting to what's next (the squaring trick → RSA)

Katz & Lindell, Introduction to Modern Cryptography (3rd ed.), the number-theory and RSA chapters Look ahead, don't dive in yet. The exponentiation-by-squaring engine you built for Fibonacci (§19.5, Case Study 2) becomes modular exponentiation here — the operation that makes RSA practical (Chapters 23, 25). Skim now to see where the chapter's logarithm is headed; read in full alongside Chapter 23.

Suggested order

  1. Re-read §§19.2–19.3 here, then read CLRS Ch. 4 (§§4.3–4.5) for the same material at full rigor and more worked recurrences.
  2. Do Rosen §8.3 exercises for additional Master-Theorem drill.
  3. For the proof of the Master Theorem, read CLRS §4.6 and attempt the Deep Dive (this chapter's exercises 19.34–19.35).
  4. For the Fibonacci payoff, read Concrete Mathematics §6.6; then explore OEIS A000045 for identities to test-and-prove.
  5. Save Akra–Bazzi (CLRS or the original paper) for when you meet a recurrence with unequal splits.
  6. Skim Katz–Lindell's RSA chapter to see the squaring trick's destination; return to it at Chapter 23.