Skip to content
Tutorials Center
My learning

Topics

Lesson 28 of 68 ยท Sequences, Sums and Recurrences

Recurrence Relations

Define sequences recursively, model problems with recurrences, study Fibonacci and the Tower of Hanoi, and compute terms with recursion, memoization and loops.

Some sequences are easiest to describe by a rule that refers to earlier terms: "each month's rabbits are the sum of the last two months", "moving a tower of n disks takes twice the moves for n โˆ’ 1 disks, plus one". Such a rule is a recurrence relation. Along with starting values it pins down the entire sequence, and it mirrors what a recursive function does, which is why recurrences are the natural language for counting problems and for algorithm running times.

In this lesson you will write recurrences for Fibonacci numbers and the Tower of Hanoi, model several everyday problems, and compute terms three ways: plain recursion, memoization and iteration. Turning a recurrence into a closed-form formula comes in Solving Recurrences. The sums behind many of these examples are in Sequences and Summations.

What is a recurrence?

A recurrence relation defines aโ‚™ using some of aโ‚€, ..., aโ‚™โ‚‹โ‚. It needs initial conditions (starting values) to be complete; otherwise many sequences satisfy it. Two quick examples:

  • aโ‚™ = aโ‚™โ‚‹โ‚ + 4 with aโ‚€ = 3 gives 3, 7, 11, ... (an arithmetic sequence).
  • aโ‚™ = 2ยทaโ‚™โ‚‹โ‚ with aโ‚€ = 5 gives 5, 10, 20, ... (a geometric sequence).

The order of a recurrence is how far back it looks. A relation like aโ‚™ = aโ‚™โ‚‹โ‚ + aโ‚™โ‚‹โ‚‚ has order 2 and needs two initial values. It is linear when earlier terms appear only multiplied by constants and added, and homogeneous when there is no extra term besides those.

Compound interest is a recurrence too: with a 5 percent yearly rate, the balance after a year is the old balance times 1.05, so 1000 becomes 1050, then 1102.5, then about 1157.63, always growing geometrically.

Anatomy of a recurrence

Initial values Where the sequence starts.
Rule How a term depends on earlier ones.
Order How many previous terms the rule uses.

Rule plus initial values determines every term.

1 / 2

Fibonacci numbers

The Fibonacci sequence is defined by Fโ‚€ = 0, Fโ‚ = 1 and Fโ‚™ = Fโ‚™โ‚‹โ‚ + Fโ‚™โ‚‹โ‚‚, giving 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... It turns up in counting problems: the number of ways to climb n stairs taking one or two steps at a time is Fโ‚™โ‚Šโ‚, and the number of bit strings of length n with no two consecutive zeros is Fโ‚™โ‚Šโ‚‚. The reasoning is a recurrence: such a string either ends in 1 (what is left is any valid string of length n โˆ’ 1) or ends in 10 (what is left is a valid string of length n โˆ’ 2).

The definition translates straight into code. Counting how many calls the naive version makes shows a problem: it recomputes the same values again and again.

Python Naive recursion, memoization and a loop

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The naive version makes 177 calls for n = 10, 21,891 for n = 20 and 242,785 for n = 25. The number of calls itself obeys a Fibonacci-like recurrence, so the cost grows exponentially. Memoization stores each result the first time it is computed (lru_cache does this for you), so each value is computed once and the work becomes linear. The loop keeps only the last two values and uses constant memory. All three agree that Fโ‚‰โ‚€ = 2880067194370816120.

The Tower of Hanoi

The puzzle has three pegs and n disks of different sizes stacked on the first peg, smallest on top. You may move one disk at a time and never place a larger disk on a smaller one. How many moves are needed to transfer the tower to another peg?

Let Hโ‚™ be the minimum number of moves. To move n disks you must first move the top n โˆ’ 1 disks off the largest one (Hโ‚™โ‚‹โ‚ moves), then move the largest disk (1 move), then bring the n โˆ’ 1 disks on top of it (Hโ‚™โ‚‹โ‚ moves again). So

Hโ‚™ = 2ยทHโ‚™โ‚‹โ‚ + 1, Hโ‚€ = 0

which gives 0, 1, 3, 7, 15, 31, 63, ... The pattern is Hโ‚™ = 2โฟ โˆ’ 1. The recursive solution is also the algorithm.

Python Solving Hanoi and counting moves

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For three disks the program prints seven moves, starting with A to C and ending with A to C. The check confirms Hโ‚™ = 2โฟ โˆ’ 1 for n up to 10 (a proof by induction is easy). The legend of a 64-disk tower is hopeless at one move per second: 2โถโด โˆ’ 1 is 18,446,744,073,709,551,615 moves.

Modeling problems with recurrences

The skill that matters is turning a story into a recurrence. A reliable method has three steps:

  1. Name the quantity: "aโ‚™ is the number of ways for size n".
  2. Split by the last decision (or the first), so each case reduces to a smaller instance.
  3. Add the counts of the cases, and compute small values by hand to get initial conditions.

For the stairs problem, the last step is either 1 stair or 2, so wโ‚™ = wโ‚™โ‚‹โ‚ + wโ‚™โ‚‹โ‚‚ with wโ‚€ = wโ‚ = 1. For bit strings of length n avoiding "00", see above: the count cโ‚™ satisfies cโ‚™ = cโ‚™โ‚‹โ‚ + cโ‚™โ‚‹โ‚‚ with cโ‚ = 2 and cโ‚‚ = 3. Always check the recurrence against brute-force enumeration for small n.

Python Check a recurrence against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two columns match for lengths 1 to 8 (2, 3, 5, 8, 13, 21, 34, 55). The interest loop prints 1050.0, 1102.5 and 1157.63. Matching small cases is a strong sanity check; a proof still needs the argument that the case split covers everything exactly once.

Recursion in code and recurrences in math are two views of the same thing. A function that calls itself on smaller inputs has a running time described by a recurrence, which you will solve for divide-and-conquer algorithms in the next lesson.

Types of recurrence relations

Recurrences come in families, and the family tells you which solving method to reach for. Four questions classify almost any recurrence.

  1. Order: how far back does it reach? a_n = 2a_{n-1} + 1 has order 1; Fibonacci a_n = a_{n-1} + a_{n-2} has order 2; a_n = a_{n-1} + a_{n-2} + a_{n-3} has order 3. The order is the gap between the largest and smallest index used.
  2. Linear or non-linear: in a linear recurrence each earlier term appears only to the first power, multiplied by a coefficient and added. a_n = a_{n-1} ยท a_{n-2} and a_n = a_{n-1}ยฒ are non-linear; they usually have no closed form.
  3. Homogeneous or non-homogeneous: a linear recurrence is homogeneous if every term involves some a_k; any extra piece f(n) that does not (a constant, n, 2^n) makes it non-homogeneous. Compare a_n = 3a_{n-1} (homogeneous) with a_n = 3a_{n-1} + 5 (non-homogeneous).
  4. Constant or variable coefficients: a_n = 2a_{n-1} + 3a_{n-2} has constant coefficients; a_n = n ยท a_{n-1} (factorials) has a coefficient that changes with n.

The word degree is sometimes used for the highest power of the terms a_k; linear recurrences have degree 1.

Recurrence Order Linear? Homogeneous? Coefficients
a_n = 5a_{n-1} 1 yes yes constant
a_n = a_{n-1} + a_{n-2} 2 yes yes constant
a_n = 2a_{n-1} + 3^n 1 yes no constant
a_n = n ยท a_{n-1} 1 yes yes variable
a_n = a_{n-1}ยฒ + 1 1 no n/a n/a
T(n) = 2T(n/2) + n divide and conquer yes no see the Master Theorem

Why does the classification matter? Linear homogeneous recurrences with constant coefficients are the friendly case. They have a characteristic equation, and their solutions form a vector space: if two sequences satisfy the recurrence, so does any combination cโ‚s + cโ‚‚t. Non-homogeneous ones are solved by adding a particular solution to the homogeneous solution. Variable-coefficient and non-linear ones need special tricks, or generating functions. The full solution methods are in Solving Recurrences.

The superposition property gives a practical test of linearity and homogeneity. Generate two sequences from different start values, combine them, and see whether the combination still satisfies the recurrence.

Python Does superposition hold? Testing linear, non-homogeneous and non-linear recurrences

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Only the two homogeneous constant-coefficient recurrences and the factorial recurrence survive superposition: they are linear and homogeneous (the factorial one is linear homogeneous with a variable coefficient). The non-homogeneous recurrence breaks because the constant 5 does not scale with the combination, and the squaring recurrence breaks because (2s + 5t)ยฒ โ‰  2sยฒ + 5tยฒ.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What do you need, besides the rule aโ‚™ = aโ‚™โ‚‹โ‚ + aโ‚™โ‚‹โ‚‚, to define a sequence uniquely?

    The rule has order 2, so it needs two starting values such as F0 = 0 and F1 = 1.
  2. 2. Why is naive recursive Fibonacci so slow?

    fib(n-1) and fib(n-2) share subproblems, so the number of calls grows exponentially. Memoization removes the repetition.
  3. 3. What is the minimum number of moves to solve the Tower of Hanoi with 5 disks?

    H(n) = 2^n - 1, so H(5) = 31.
  4. 4. In how many ways can you climb 5 stairs using steps of 1 or 2?

    w(n) = w(n-1) + w(n-2) with w(0) = w(1) = 1 gives 1, 1, 2, 3, 5, 8. For n = 5 the answer is 8.
  5. 5. What does lru_cache do for a recursive function?

    It remembers previous return values, so each argument is computed only once.

Summary

  • A recurrence defines each term from earlier ones; initial conditions complete the definition.
  • Fibonacci (Fโ‚™ = Fโ‚™โ‚‹โ‚ + Fโ‚™โ‚‹โ‚‚) and Hanoi (Hโ‚™ = 2Hโ‚™โ‚‹โ‚ + 1 = 2โฟ โˆ’ 1) are the standard examples.
  • Model a problem by naming the quantity, splitting on the last decision and adding the cases.
  • Naive recursion can repeat work exponentially; memoization or a loop makes it linear.
  • Check any recurrence against brute force for small n before relying on it.

Next: Solving Recurrences, finding closed forms for what you just defined.