How many moves does it take to solve the Tower of Hanoi? The answer comes from a recurrence relation, which writes the problem in terms of itself with one disk fewer. We set up recurrences and solve them by substitution, by the characteristic equation and by the Master Theorem, used for merge sort.
What if the step depends on more than one earlier case, as in Fibonacci? Strong induction assumes all the earlier cases. We will see the technique at work on prime factorization, the chocolate bar, postage stamps and Binet’s formula, which in floating point fails from the 71st term on.
How do you prove a formula holds for every natural number, if there are infinitely many of them? With mathematical induction. This introduction maps out the series: classic induction, strong induction and recurrence relations, from Fibonacci to the Tower of Hanoi.
