Further Reading: Sequences and Summations

Annotated pointers for going deeper. Start with the textbook sections to shore up the mechanics, then follow whichever thread pulls you — the art of finding closed forms, the algorithm-analysis payoff, or the Fibonacci story this chapter only began.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §2.4 ("Sequences and Summations") The market-standard, drill-heavy treatment of sequence notation, summation manipulation, and the arithmetic and geometric series. If you want more mechanical practice than this chapter's exercises provide — especially index-shifting and double sums — this is the place to find it.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Sums and Asymptotics" Freely available. The most CS-flavored presentation in print: sums are developed hand-in-hand with their use in running-time analysis, including the "bound a sum by an integral" technique that makes the harmonic-number estimate $H_n \approx \ln n$ precise. Read it for the bridge from §11.6 to Chapter 14.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapters 1–2 The definitive treatment of sums. Chapter 2 builds a whole "finite calculus" on the telescoping idea of §11.4 — the discrete analogue of differentiation and integration — and introduces the perturbation method, a systematic way to derive closed forms (it is exactly the "multiply and subtract" trick of §11.3, generalized). Denser than this chapter, but the natural next step if you enjoyed deriving formulas rather than memorizing them.

On the algorithm-analysis payoff

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), Appendix A ("Summations") A compact reference for exactly the sums that arise in analyzing algorithms: arithmetic, geometric, harmonic, and the bounding techniques. Pair it with §11.6; this appendix is what practitioners actually flip back to when collapsing a loop's cost.

Knuth, The Art of Computer Programming, Vol. 1 (3rd ed.), §1.2.3 ("Sums and Products") and §1.2.5 ("Permutations and Factorials") The deepest treatment of summation and product manipulation, and of factorials and their growth (including a careful look at Stirling's approximation, the precise statement of "how fast $n!$ grows" hinted at in §11.5). Reach for it when you want the full rigor behind a formula this chapter stated.

On the Fibonacci thread

OEIS — The On-Line Encyclopedia of Integer Sequences, sequence A000045 (Fibonacci) Free online. Dozens of identities involving the Fibonacci numbers, many of which make excellent "conjecture and test, then prove" exercises in the spirit of this chapter. A good place to find a sequence-summation pattern and try to collapse it before Chapter 18 solves the recurrence outright.

Levin, Discrete Mathematics: An Open Introduction (3rd ed.), the "Sequences" chapter Freely available. A gentle, free companion that develops sequences, the difference between closed-form and recursive descriptions, and arithmetic/geometric series with a light touch and many worked examples. Good if any part of §11.1 felt fast.

Suggested order

  1. Re-read §§11.2–11.4 here, then work the Rosen §2.4 exercises for drill on notation and index shifts.
  2. Read the MIT 6.042 "Sums and Asymptotics" chapter for the CS framing and the integral-bound estimate of $H_n$ — it connects §11.4 and §11.6 directly to Chapter 14.
  3. Keep CLRS Appendix A beside you while doing the §11.6 and Case Study exercises; it is a working reference, not a read-through.
  4. Save Concrete Mathematics Chapters 1–2 for when you want to derive closed forms systematically (finite calculus, the perturbation method) rather than look them up — the 🔬 Deep Dive path.