A recurrence gives each term of a sequence from the terms before it, together with starting values. To set one up, name the count an, look at the first or the last step, and split into cases that are smaller copies of the same problem. The Tower of Hanoi, regions cut by lines, staircases, tilings and strings all lead to recurrences, often the Fibonacci one.
about 30 min
Lesson 1 of 3Show all lessonsHide
Try the code and the simulations beside the lesson.
What you will be able to do
describe a count by a recurrence and its starting values;
set up a recurrence by splitting on the first or the last step;
solve a first-order recurrence by unrolling it.
A tower of discs
Three pegs stand in a row. On the first peg sits a tower of n discs, the largest at the bottom. You may move one disc at a time from peg to peg, and a disc may never sit on a smaller disc. What is the fewest number of moves that takes the whole tower to the third peg?
Let hn be that number. Try small towers. One disc takes 1 move. Two discs take 3 moves: small disc aside, large disc across, small disc on top.
Now think about the largest disc. It can move only when the other n−1 discs sit together on one other peg. So:
move the top n−1 discs to the middle peg: hn−1 moves;
move the largest disc to the third peg: 1 move;
move the n−1 discs on top of it: hn−1 moves.
This gives the recurrence
hn=2hn−1+1,h1=1.
A recurrence is a rule that gives each term from earlier terms, together with starting values (also called initial conditions). The steps above show that 2hn−1+1 moves are enough. They are also needed, because the largest disc must move at least once, with the other discs moved off and back on.
Three pegs in a row. In the first picture four discs sit on the left peg, largest at the bottom. In the second, the top three discs have moved to the middle peg and the largest disc is moving to the right peg, shown by an arrow. In the third, the three discs are moving onto the largest disc on the right peg. Labels say: h of n minus 1 moves, then 1 move, then h of n minus 1 moves.
Unrolling a first-order recurrence
A recurrence that uses only the term before is called first order. We can often solve it by unrolling. Add 1 to both sides of hn=2hn−1+1:
hn+1=2(hn−1+1).
So hn+1 doubles each time. It starts at h1+1=2, so hn+1=2n and
hn=2n−1.
Check: h2=3, h3=7, h4=15. A proof by induction confirms the formula for every n, as in the chapter on mathematical induction.
Regions cut by lines
Draw n straight lines in a plane, with no two parallel and no three through one point. Let rn be the number of regions. No line gives r0=1 region.
The nth line crosses the n−1 old lines in n−1 different points. Those points cut the new line into n pieces. Each piece splits one old region into two. So
rn=rn−1+n.
Unrolling, rn=1+(1+2+⋯+n)=1+2n(n+1). Four lines give 11 regions.
Staircases and the Fibonacci numbers
You climb a staircase of n steps, taking one step or two steps at a time. Let wn be the number of ways. Split on the last move.
If the last move is one step, the moves before it climb n−1 steps: wn−1 ways.
If the last move is two steps, the moves before it climb n−2 steps: wn−2 ways.
The two cases do not overlap and cover every way, so
wn=wn−1+wn−2,w1=1,w2=2.
This is the Fibonacci recurrence. The Fibonacci numbers are F1=1, F2=1 and Fn=Fn−1+Fn−2, which gives 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So wn=Fn+1. Some books start with F0=0, which gives the same list one place later, so always check the starting values.
Tilings and strings
The same recurrence counts two other things.
Tilings. A strip of 2 rows and n columns is covered with 1×2 dominoes. Look at the left end: one upright domino leaves a 2×(n−1) strip, or two flat dominoes leave a 2×(n−2) strip. So tn=tn−1+tn−2, with t1=1 and t2=2.
Strings. Count strings of n digits 0 and 1 with no two 1s next to each other. A string ends in 0, after any good string of length n−1. Or it ends in 01, after any good string of length n−2. So sn=sn−1+sn−2, with s1=2 and s2=3.
Two rows of strips of 2 rows of cells. The top row shows the five ways to tile a 2 by 4 strip with dominoes: upright dominoes are blue and pairs of flat dominoes are orange. The bottom row shows how a tiling starts: an upright domino at the left leaves a 2 by 3 strip, or two flat dominoes at the left leave a 2 by 2 strip.
The method
Name the count. Let an be the answer for size n.
Split on the first or the last step. Each case should be a smaller copy of the same question.
Check the cases. They must not overlap, and together they must cover everything.
Find the starting values by counting small cases by hand.
Work forward in a table, or solve the recurrence.
Practise with new numbers
Try it in Python
The program counts the staircase ways in two ways: by the recurrence, and by listing every sequence of moves. The two answers agree.
Common mistakes
Overlapping cases. If a way is counted in two cases, the recurrence counts too many.
Wrong starting values.w2=2, not 1: two single steps, or one double step.
Splitting on a step that is not a smaller copy. After the first move, the rest must be the same kind of problem.
Mixing up conventions.F1=F2=1 here. With F0=0, the index is the same; with F1=1 and F2=2, it shifts.
Remember these
A recurrence gives each term from earlier terms, plus starting values.
Tower of Hanoi: hn=2hn−1+1, so hn=2n−1.
Lines: rn=rn−1+n, so rn=1+2n(n+1).
Steps of 1 or 2, domino tilings and strings with no 11 all follow the Fibonacci recurrence.
Check yourself
Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
How many moves does the Tower of Hanoi need for 5 discs?
Into how many regions do 6 lines cut the plane, if no two are parallel and no three meet in one point?
In how many ways can you climb 8 steps, one or two at a time?
Write a recurrence for cn, the number of ways to pay n coins' worth using coins of value 1 and 3, where the order of payment matters.
A student writes sn=sn−1+sn−2 for strings with no two 1s together and uses s1=1, s2=2. What is wrong?
References
R. A. Brualdi, Introductory Combinatorics, Chapter 7, recurrence relations.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Chapter 1, recurrent problems.
Enroll free in Recurrences and Counting by Recursion
Every lesson is open to read. Enrolling also lets you:
Mark lessons done and carry on where you stopped.
Take the tests of this lesson and its course.
Count the course towards the certificate for its chapter.