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.
If the first domino falls and each domino knocks over the next, they all fall. That is the logic of the Principle of Mathematical Induction. We will see the structure of the proof (base case, hypothesis and step) in sums, divisibility and inequalities, and the false proof that all horses are the same color.
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.
