Section 30.3

Recursion and Induction

Josephus, Tower of Hanoi, puzzles solved by working backward.

Toolkit

Many “process” puzzles become tractable by expressing the state after $n$ steps in terms of the state after $n-1$ steps, or by reversing time and running the mechanics backward from a known terminal configuration. Key tools:

Recurrence from decomposing a size- $n$ task into smaller subtasks: find $T(n)=f(T(n-1))$ , solve by unrolling or guessing-and-verifying a closed form.
For elimination/survivor processes, look for an invariant structure that recurs at a smaller scale (e.g. powers of two), giving: write $N = 2^m + r$ , and the survivor is determined by $r$ relative to the power-of-two base case.
When a quantity (total money, total count) is conserved, reconstruct the sequence by inverting each step from the known final state, undoing one move at a time.
Always verify a closed-form guess by checking it satisfies both the recurrence and the base case.

Problems

30.13 Tower of Hanoi Easy Free
30.14 Deleting Every Other Number Medium
30.15 Josephus Problem Medium
30.16 Doubling Stacks Working Backward Medium