TAOCP 1.2.1 Mathematical Induction: reading guide

Induction as the main tool for proving things about integers and about programs. Knuth goes further than a typical math class by showing how to prove an algorithm correct by attaching assertions to each step of a flowchart, using an extended version of Euclid's algorithm as the worked example.

Time About 6 hours this week

Why it matters

Loop invariants, the thing that makes binary search and in-place algorithms correct, are induction in disguise. Once you can write the invariant, debugging off-by-one errors gets a lot less random.

Before you start

1.1 Algorithms
Basic induction proofs (week 0)

How to approach it

Read the basic induction material quickly if you have seen it before. Slow way down for the flowchart-with-assertions proof of the extended Euclid algorithm: copy the flowchart onto paper and check every assertion yourself, step by step. That technique is the payoff of the section.

Exercises

Some of the early exercises hand you a "proof" that looks fine but proves something false; find the hole before reading the answer, it is great training for code review. Do every exercise rated 00 to 20 in your head or on paper; they are quick and they check you actually absorbed the definitions. Then pick two or three rated 20 to 25 (M or not) and grind them out fully. Attempt one M25 to M30 and give yourself a hard 90-minute cap before reading the answer. Always read the answer to every exercise you attempted, even the ones you got, because Knuth's answers often teach a second technique.

Traps

Forgetting the base case or proving the step only for large n.
Strengthening the hypothesis is often the trick: if the induction step will not go through, try proving something stronger.
Reading the assertion proof without actually checking each arrow. You will not absorb it passively.