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
  1. Notes
  2. /Recurrences and Counting by Recursion: Quick Revision
Mathematics

Recurrences and Counting by Recursion: Quick Revision

A brief note on recurrences: setting one up, the Tower of Hanoi, Fibonacci counts, the characteristic equation, repeated roots, fixed points, derangements and Catalan numbers. With practice, a program and questions to check yourself.

StemPy LabWritten by StemPy Lab
Log in to save

A brief note on Recurrences and Counting by Recursion. Read it before a test. Try each question at the end before you open its answer.

Setting up

  • Name the count ana_nan​ for size nnn.
  • Split on the first or the last step. Each case must be a smaller copy, with no overlaps.
  • Starting values: count the smallest cases by hand.
  • 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 in a plane: 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 1 or 2, domino tilings, strings with no 11: the Fibonacci recurrence.

Solving

  • Characteristic equation of an=pan−1+qan−2a_n = pa_{n-1} + qa_{n-2}an​=pan−1​+qan−2​: x2=px+qx^2 = px + qx2=px+q.
  • Different roots r,sr, sr,s: an=Arn+Bsna_n = Ar^n + Bs^nan​=Arn+Bsn.
  • Double root rrr: an=(A+Bn)rna_n = (A + Bn)r^nan​=(A+Bn)rn.
  • Constant term in an=can−1+da_n = ca_{n-1} + dan​=can−1​+d: fixed point L=cL+dL = cL + dL=cL+d, then an−L=cn(a0−L)a_n - L = c^n(a_0 - L)an​−L=cn(a0​−L).
  • Binet: Fn=φn−ψn5F_n = \dfrac{\varphi^n - \psi^n}{\sqrt{5}}Fn​=5​φn−ψn​, with φ≈1.618\varphi \approx 1.618φ≈1.618.

Special numbers

  • Derangements: Dn=(n−1)(Dn−1+Dn−2)D_n = (n - 1)(D_{n-1} + D_{n-2})Dn​=(n−1)(Dn−1​+Dn−2​), D1=0D_1 = 0D1​=0, D2=1D_2 = 1D2​=1; nearest whole number to n!e\dfrac{n!}{e}en!​.
  • Exactly kkk fixed: (nk)Dn−k\dbinom{n}{k}D_{n-k}(kn​)Dn−k​.
  • Catalan: Cn=1n+1(2nn)C_n = \dfrac{1}{n + 1}\dbinom{2n}{n}Cn​=n+11​(n2n​): brackets, diagonal paths, triangulations of an (n+2)(n + 2)(n+2)-gon.

A worked example

Solve an=an−1+12an−2a_n = a_{n-1} + 12a_{n-2}an​=an−1​+12an−2​ with a0=2a_0 = 2a0​=2 and a1=1a_1 = 1a1​=1.

  1. Equation. x2=x+12x^2 = x + 12x2=x+12, roots 444 and −3-3−3.
  2. Fit. A+B=2A + B = 2A+B=2 and 4A−3B=14A - 3B = 14A−3B=1, so A=1A = 1A=1 and B=1B = 1B=1.
  3. Answer. an=4n+(−3)na_n = 4^n + (-3)^nan​=4n+(−3)n.

Practice with new numbers

A program to try

The program checks three answers by listing every case.

Read it first. Then run it. Which recurrence does each count follow?

1. Change the 7 in the first part to 9. Predict the new count from the Fibonacci numbers first.

Mistakes to avoid

  • Overlapping cases in the split.
  • Wrong starting values, such as w2=1w_2 = 1w2​=1 for steps of 111 or 222.
  • Arn+BsnAr^n + Bs^nArn+Bsn with a double root.
  • n!−1n! - 1n!−1 in place of DnD_nDn​.
  • CnC_nCn​ for an nnn-gon. An nnn-gon has Cn−2C_{n-2}Cn−2​ triangulations.

Check yourself

  1. How many moves does the Tower of Hanoi need for 666 discs?
  1. Solve an=5an−1−4an−2a_n = 5a_{n-1} - 4a_{n-2}an​=5an−1​−4an−2​ with a0=2a_0 = 2a0​=2 and a1=5a_1 = 5a1​=5.
  1. Find D5D_5D5​.
  1. How many balanced strings of 333 pairs of brackets are there?
  1. Solve an=4an−1−4an−2a_n = 4a_{n-1} - 4a_{n-2}an​=4an−1​−4an−2​ with a0=3a_0 = 3a0​=3 and a1=8a_1 = 8a1​=8.

Sources

  • R. A. Brualdi, Introductory Combinatorics, Chapters 6, 7 and 8.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Chapters 1 and 6.
← All Notes
← The Pigeonhole Principle: Quick RevisionGraph Theory: Quick Revision →
More onPigeonhole Principle, Recursion and Graph Theory

Discussion (0)

Log in to join the discussion.

Loading…

On this page

  1. Setting up
  2. Solving
  3. Special numbers
  4. A worked example
  5. Practice with new numbers
  6. A program to try
  7. Mistakes to avoid
  8. Check yourself
  9. Sources

Goes with the lesson

  1. Derangements and Catalan numbersRecurrences and Counting by Recursion

More notes on this topic

  1. Graph Theory: Quick Revision
  2. The Pigeonhole Principle: Quick Revision
All notes on this topic →