Further Reading: Mathematical Induction

Annotated pointers for going deeper. Start with the textbook sections, then branch out as your interest (proof technique, recursion, program correctness) pulls you.

Core textbook treatments

Rosen, Discrete Mathematics and Its Applications (8th ed.), §5.1–5.2 The market-standard treatment of mathematical and strong induction, with a large, well-graded exercise bank. If you want more drill problems than this chapter provides, this is the place.

Lehman, Leighton & Meyer, Mathematics for Computer Science (MIT 6.042), "Induction" chapters Freely available. The most CS-flavored presentation in print: induction is developed alongside program correctness and recurrences, with the same "induction is how you reason about recursion" spirit as this chapter. Highly recommended as a companion.

Graham, Knuth & Patashnik, Concrete Mathematics (2nd ed.), Chapter 1 Induction in the service of finding and proving closed-form sums. Denser, but it rewards the effort and shows induction as a working tool, not a ceremony.

On recursion and induction together

Velleman, How to Prove It (3rd ed.), the induction chapter The gentlest careful treatment of proof-writing anywhere. If the form of proofs still feels shaky, this book is the standard recommendation, and its induction chapter pairs perfectly with ours.

Abelson & Sussman, Structure and Interpretation of Computer Programs, §1.2 Freely available. On "recursive processes" and how to reason about them. Reading it alongside §6.4 will cement why the recursive call is the inductive hypothesis.

On program correctness and loop invariants

Cormen, Leiserson, Rivest & Stein (CLRS), Introduction to Algorithms (4th ed.), §2.1 Introduces loop invariants exactly as we use them (initialization / maintenance / termination) and applies them to insertion sort. The canonical reference for the technique in §6.5.

"Nearly All Binary Searches and Mergesorts Are Broken" (Joshua Bloch, Google Research Blog, 2006) Free online. The famous account of a real binary-search overflow bug that survived for years. A visceral argument for why stating and checking loop invariants matters in production code.

Fun and depth

"The Fibonacci sequence" — entries in the OEIS (oeis.org, sequence A000045) The Online Encyclopedia of Integer Sequences entry for Fibonacci, with dozens of identities (many provable by induction). A great source of "conjecture and test, then prove" exercises.

3Blue1Brown, "Olympiad-level counting" and induction explainers (YouTube) Free. Visual intuition for inductive and combinatorial arguments. Good for building the "why," especially the geometric picture behind the sum-of-odds and sum-of-cubes identities.

Suggested order

  1. Re-read §§6.2–6.4 here, then do Rosen §5.1 exercises for drill.
  2. Read the MIT 6.042 induction chapter for the CS framing.
  3. Read CLRS §2.1 and the Bloch blog post before tackling the loop-invariant exercises.
  4. Save Concrete Mathematics Ch. 1 for after Chapter 11 (summations).