In algebra you met recursive formulas given to you. Here you build them. Many counting problems are hard to attack head-on but easy once you notice that a big object is a small object with one more piece. That is the sum rule again, and strong induction is what makes the recurrence trustworthy.
Key idea
To set up a recurrence for $a_{n}$, split the objects of size $n$ by how they end (their last piece). Each case should leave a smaller object of the same kind, counted by an earlier term. Add the cases, and state enough starting values for the recurrence to run.
Why it works
Take tilings of a 1-by-$n$ strip with squares and dominoes. The last tile is either a square, leaving a strip of length $n - 1$ tiled in any of $a_{n-1}$ ways, or a domino, leaving length $n - 2$ in $a_{n-2}$ ways. These cases cannot overlap and cover everything, so $a_{n} = a_{n-1} + a_{n-2}$. Since the recurrence reaches back two steps, it needs two starting values: $a_{1} = 1$ and $a_{2} = 2$.
Worked examples
Worked example: Tilings
How many ways are there to tile a 1-by-$6$ strip with squares and dominoes?
- Recurrence $a_{n} = a_{n-1} + a_{n-2}$ with $a_{1} = 1$, $a_{2} = 2$.
- $a_{3} = 3$, $a_{4} = 5$, $a_{5} = 8$, $a_{6} = 13$.
Answer: $13$
Worked example: Strings with no two 1s in a row
Let $b_{n}$ count bit strings of length $n$ with no two 1s next to each other. Set up a recurrence and find $b_{5}$.
- Split by the end. If the string ends in 0, the first $n - 1$ bits can be any good string: $b_{n-1}$.
- If it ends in 1, the bit before must be 0, so it ends in 01, and the first $n - 2$ bits can be any good string: $b_{n-2}$.
- So $b_{n} = b_{n-1} + b_{n-2}$, with $b_{1} = 2$ (0, 1) and $b_{2} = 3$ (00, 01, 10).
- $b_{3} = 5$, $b_{4} = 8$, $b_{5} = 13$.
Answer: $b_{n} = b_{n-1} + b_{n-2}$; $b_{5} = 13$
Worked example: The Tower of Hanoi
Disks of $n$ sizes sit on a peg, largest at the bottom. Move them to another peg, one at a time, never putting a disk on a smaller one. Find a recurrence for the fewest moves $h_{n}$.
- The largest disk must move at some point, and when it does, the other $n - 1$ disks must all be on the third peg.
- So: move $n - 1$ disks out of the way ($h_{n-1}$ moves), move the largest ($1$), then move the $n - 1$ disks on top of it ($h_{n-1}$).
- $h_{n} = 2h_{n-1} + 1$ with $h_{1} = 1$, giving $1, 3, 7, 15, 31, \ldots$
Answer: $h_{n} = 2h_{n-1} + 1$, $h_{1} = 1$
Common mistake
Missing a way the pattern can end, or forgetting starting values. Counting only tilings that end in a square gives $a_{n} = a_{n-1}$, which says every length has just one tiling. And $a_{n} = a_{n-1} + a_{n-2}$ alone does not determine a sequence: with $a_{1} = 2$, $a_{2} = 3$ you get the bit strings, not the tilings. Check: list all cases for small $n$ by hand and make sure the recurrence reproduces them.