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.
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.
In how many ways can you choose a valid password? What is the shortest path between two cities? These are questions of discrete mathematics. This roadmap introduces the site’s four series on the topic: sets, induction and recurrence, combinatorics, and graphs, with 28 articles.
