In one sentence
A big problem has a smaller copy of itself hidden inside.
To find the answer for , do not count by brute force. Focus on the last step and remove it: what is left is often the same problem for (or ). That gives a link between the answers: a recurrence relation. Add the first one or two values, and every later term can be worked out step by step. To prove the pattern holds forever, use mathematical induction: the starting case holds, and each term leads to the next.
Predict first
How many ways are there to cover a 2×6 strip with 1×2 dominoes? (Make a guess by feel first.)
ways. Do not count the 2×6 strip directly: start small, and watch how each term “grows” out of the ones before it.
Example: the number of tilings of a 2×n strip
Step 1 / 6- The smallest case
A 2×1 strip fits just one upright domino: .
The rule of thumb for finding a recurrence: ask how many ways the last step can go, and what each one shrinks the problem to.
Stop 1 · Counting (Vol. 7)
Draw lines in the plane so that every two of them cross and no three pass through one point. How many regions do they cut the plane into?
Predict first
such lines cut the plane into regions. Add a th line: how many regions now?
The th line is cut by the first into pieces, and each piece splits one region into two. So there are more regions: .
Example: n lines cutting up the plane
Step 1 / 5- Starting value
With no lines, the plane is whole region.
Stop 2 · Operations and games (Vol. 7)
The Tower of Hanoi: three pegs, and discs of different sizes stacked on the first peg, largest at the bottom. You may move only one disc at a time, and a larger disc may never sit on a smaller one. What is the fewest number of moves needed to move the whole stack to the third peg?
Example: the fewest moves for the Tower of Hanoi
Step 1 / 5- Starting value
With just disc, it takes move.
Why can it not be done in fewer moves? The largest disc must move at least once. Before it moves, the other discs must all be stacked out of the way on another peg, which takes at least moves; after it lands, that stack must be moved back on top, which takes at least more.
Stop 3 · The Pythagorean equation (Vol. 6)
Recursion is not only for counting; it can also build infinitely many solutions: given one solution, find a way to build the next one from it.
In , the hypotenuse is just more than the longer leg. Are there other Pythagorean triples like this? How many?
Example: Pythagorean triples whose hypotenuse is 1 more than a leg
Step 1 / 5- Simplify the condition
Call the sides . Expand and cancel from both sides.
It also works backwards: if you can prove that “whenever there is a positive integer solution, there is a smaller one”, the solutions would keep getting smaller forever. But positive integers cannot keep shrinking forever, so there is no solution at all. This is called infinite descent: recursion run in reverse.
Practice
You climb stairs taking or steps at a time. How many different ways are there to climb a staircase of steps?
Stairs again, but now each stride can be , or steps. How many ways are there to climb steps?
There are circles in the plane. Every two of them cross at two points, and no three pass through one point. How many regions do they cut the plane into?