HelpContactFor teachers and institutes
>_StemPy Lab
Mock TestsClasses

>_StemPy Lab

Learn. Solve. Code the solutions. Test yourself.

Live examsFree mock exams, timed and rankedEveryone starts together, and your score and rank come the moment it ends.See the exams →
Live examsInternational live exams are comingTell us which exam you want first. Timed practice papers are open now.See what is coming →

Learn

  • Physics
  • Chemistry
  • Mathematics
  • Biology
  • Python Programming
  • Statistics & Data Science
  • Computer Science
  • Space Science and Astronomy
  • Earth and Environmental Science
  • Classes
  • Groups

Practice

  • Problems
  • Quizzes
  • Mock Tests
  • Prepare for an Exam
  • Question Sets
  • Exams
  • Certificates
  • Python Labs
  • AI Practice Generator
  • Student-Created Tests

Community

  • Discussions
  • Resources
  • Notes
  • Glossary
  • Blog

Account

  • Log in
© 2026 senLearn. All rights reserved.HelpFor SchoolsAboutContactPrivacy PolicyTerms of UseRefund Policy
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers
  1. Mathematics
  2. /Recurrences and Counting by Recursion
  3. /Setting up a recurrence

Course 30.2·Lesson 1 of 3

Setting up a recurrence

A recurrence gives each term of a sequence from the terms before it, together with starting values. To set one up, name the count ana_nan​, 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
Recurrences and Counting by Recursion
  1. 1Setting up a recurrence
  2. 2Solving linear recurrences
  3. 3Derangements and Catalan numbers

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 nnn 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 hnh_nhn​ be that number. Try small towers. One disc takes 111 move. Two discs take 333 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−1n - 1n−1 discs sit together on one other peg. So:

  1. move the top n−1n - 1n−1 discs to the middle peg: hn−1h_{n-1}hn−1​ moves;
  2. move the largest disc to the third peg: 111 move;
  3. move the n−1n - 1n−1 discs on top of it: hn−1h_{n-1}hn−1​ moves.

This gives the recurrence

hn=2hn−1+1,h1=1.\displaystyle h_n = 2h_{n-1} + 1, \quad h_1 = 1.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+12h_{n-1} + 12hn−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 111 to both sides of hn=2hn−1+1h_n = 2h_{n-1} + 1hn​=2hn−1​+1:

hn+1=2(hn−1+1).\displaystyle h_n + 1 = 2(h_{n-1} + 1).hn​+1=2(hn−1​+1).

So hn+1h_n + 1hn​+1 doubles each time. It starts at h1+1=2h_1 + 1 = 2h1​+1=2, so hn+1=2nh_n + 1 = 2^nhn​+1=2n and

hn=2n−1.\displaystyle h_n = 2^n - 1.hn​=2n−1.

Check: h2=3h_2 = 3h2​=3, h3=7h_3 = 7h3​=7, h4=15h_4 = 15h4​=15. A proof by induction confirms the formula for every nnn, as in the chapter on mathematical induction.

Regions cut by lines

Draw nnn straight lines in a plane, with no two parallel and no three through one point. Let rnr_nrn​ be the number of regions. No line gives r0=1r_0 = 1r0​=1 region.

The nnnth line crosses the n−1n - 1n−1 old lines in n−1n - 1n−1 different points. Those points cut the new line into nnn pieces. Each piece splits one old region into two. So

rn=rn−1+n.\displaystyle r_n = r_{n-1} + n.rn​=rn−1​+n.

Unrolling, rn=1+(1+2+⋯+n)=1+n(n+1)2r_n = 1 + (1 + 2 + \dots + n) = 1 + \dfrac{n(n + 1)}{2}rn​=1+(1+2+⋯+n)=1+2n(n+1)​. Four lines give 111111 regions.

Staircases and the Fibonacci numbers

You climb a staircase of nnn steps, taking one step or two steps at a time. Let wnw_nwn​ be the number of ways. Split on the last move.

  • If the last move is one step, the moves before it climb n−1n - 1n−1 steps: wn−1w_{n-1}wn−1​ ways.
  • If the last move is two steps, the moves before it climb n−2n - 2n−2 steps: wn−2w_{n-2}wn−2​ ways.

The two cases do not overlap and cover every way, so

wn=wn−1+wn−2,w1=1,w2=2.\displaystyle w_n = w_{n-1} + w_{n-2}, \quad w_1 = 1, \quad w_2 = 2.wn​=wn−1​+wn−2​,w1​=1,w2​=2.

This is the Fibonacci recurrence. The Fibonacci numbers are F1=1F_1 = 1F1​=1, F2=1F_2 = 1F2​=1 and Fn=Fn−1+Fn−2F_n = F_{n-1} + F_{n-2}Fn​=Fn−1​+Fn−2​, which gives 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So wn=Fn+1w_n = F_{n+1}wn​=Fn+1​. Some books start with F0=0F_0 = 0F0​=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.

  1. Tilings. A strip of 222 rows and nnn columns is covered with 1×21 \times 21×2 dominoes. Look at the left end: one upright domino leaves a 2×(n−1)2 \times (n - 1)2×(n−1) strip, or two flat dominoes leave a 2×(n−2)2 \times (n - 2)2×(n−2) strip. So tn=tn−1+tn−2t_n = t_{n-1} + t_{n-2}tn​=tn−1​+tn−2​, with t1=1t_1 = 1t1​=1 and t2=2t_2 = 2t2​=2.
  2. Strings. Count strings of nnn digits 000 and 111 with no two 111s next to each other. A string ends in 000, after any good string of length n−1n - 1n−1. Or it ends in 010101, after any good string of length n−2n - 2n−2. So sn=sn−1+sn−2s_n = s_{n-1} + s_{n-2}sn​=sn−1​+sn−2​, with s1=2s_1 = 2s1​=2 and s2=3s_2 = 3s2​=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

  1. Name the count. Let ana_nan​ be the answer for size nnn.
  2. Split on the first or the last step. Each case should be a smaller copy of the same question.
  3. Check the cases. They must not overlap, and together they must cover everything.
  4. Find the starting values by counting small cases by hand.
  5. 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.

Read it first. Then run it. Compare the two columns.

1. Change n_max = 10 to n_max = 16. Which column takes longer to compute, and why?

2. Change moves = [1, 2] to moves = [1, 3]. The first column is now wrong. Change its line to ways[k] = ways[k - 1] + ways.get(k - 3, 0) and run it again.

Common mistakes

  • Overlapping cases. If a way is counted in two cases, the recurrence counts too many.
  • Wrong starting values. w2=2w_2 = 2w2​=2, not 111: 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=1F_1 = F_2 = 1F1​=F2​=1 here. With F0=0F_0 = 0F0​=0, the index is the same; with F1=1F_1 = 1F1​=1 and F2=2F_2 = 2F2​=2, it shifts.

Remember these

  • A recurrence gives each term from earlier terms, plus starting values.
  • Tower of Hanoi: hn=2hn−1+1h_n = 2h_{n-1} + 1hn​=2hn−1​+1, so hn=2n−1h_n = 2^n - 1hn​=2n−1.
  • Lines: rn=rn−1+nr_n = r_{n-1} + nrn​=rn−1​+n, so rn=1+n(n+1)2r_n = 1 + \dfrac{n(n + 1)}{2}rn​=1+2n(n+1)​.
  • Steps of 111 or 222, domino tilings and strings with no 111111 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.

  1. How many moves does the Tower of Hanoi need for 555 discs?
  1. Into how many regions do 666 lines cut the plane, if no two are parallel and no three meet in one point?
  1. In how many ways can you climb 888 steps, one or two at a time?
  1. Write a recurrence for cnc_ncn​, the number of ways to pay nnn coins' worth using coins of value 111 and 333, where the order of payment matters.
  1. A student writes sn=sn−1+sn−2s_n = s_{n-1} + s_{n-2}sn​=sn−1​+sn−2​ for strings with no two 111s together and uses s1=1s_1 = 1s1​=1, s2=2s_2 = 2s2​=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.
No payment. You can leave at any time.

Problems (4)

A garden path is a row of 14 paving slabs…Hard · High School (11–12) · by StemPy Lab
Some circles are drawn in a plane. Every two of them cross in exactly two points, and no three of…Hard · High School (11–12) · by StemPy Lab
A sensor sends signals as strings of the digits 0 and 1…Advanced · High School (11–12) · by StemPy Lab
Next: lesson 2Solving linear recurrences
← Recurrences and Counting by Recursion
← PreviousSolving linear recurrences →

Discussion (0)

Log in to join the discussion.

Loading…

1 simulation
1 practice question
1 Python program
5 questions to check yourself

This lesson is free to read. Enroll free to keep your place and take the tests.

A strip of 2 rows and n columns is covered with tiles, with no gaps and no overlaps…
Advanced · High School (11–12) · by StemPy Lab

Python Labs (1)

Counting by recursionPython Lab · by StemPy Lab