Skip to content
Tutorials Center
My learning

Topics

Lesson 29 of 68 · Sequences, Sums and Recurrences

Solving Recurrences

Turn a recurrence into a closed form by unrolling, characteristic equations and the Master theorem, and check every answer numerically in Python.

A recurrence relation describes each term of a sequence using earlier terms. That is a fine definition, but it is a slow way to compute: to find the millionth term you must find all the ones before it. Solving a recurrence means finding a closed form, a formula that gives the n-th term directly. It also answers questions like "how fast does this algorithm grow?" at a glance.

There is no single method that cracks every recurrence. In this lesson you learn three that cover most of what appears in practice: unrolling (repeated substitution), the characteristic equation for linear recurrences, and the Master theorem for divide-and-conquer algorithms. After each, you will verify the answer with a few lines of Python, because a guessed formula that has not been tested is only a guess.

Three tools for recurrences

Unrolling Substitute again and again, then spot the pattern.
Characteristic equation For linear recurrences with constant coefficients.
Master theorem For divide and conquer: T(n) = aT(n/b) + f(n).

Always check the closed form against the first terms.

1 / 2

Unrolling

Unrolling means writing the recurrence for the previous term, substituting it back in, and repeating until a pattern appears. Take T(n) = T(n-1) + n with T(0) = 0:

Text
T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     ...
     = T(0) + 1 + 2 + ... + n

The pattern is a sum, and you know that 1 + 2 + ... + n = n(n+1)/2. So the closed form is T(n) = n(n+1)/2. A second example is the Tower of Hanoi, H(n) = 2H(n-1) + 1 with H(0) = 0. Unrolling gives H(n) = 2^(n-1) + ... + 2 + 1, a geometric sum equal to 2^n - 1.

Unrolling does not prove the formula, because "spot the pattern" is a leap. A rigorous proof uses mathematical induction. What you can do immediately is compare the formula against the recurrence for many values of n.

Python Unroll, guess, then verify

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 check passes for every tested n. It is not a proof, but a wrong formula would almost always fail within the first few values.

Linear recurrences with constant coefficients

Many sequences satisfy a recurrence such as a(n) = 5a(n-1) - 6a(n-2): each term is a fixed combination of the previous terms, with no extra function of n added. For these, there is a systematic method.

Idea: try a solution of the form a(n) = r^n. Substituting into a(n) = c1·a(n-1) + c2·a(n-2) and dividing by r^(n-2) gives the characteristic equation:

r² = c1·r + c2

The method then depends on the roots:

  • Two distinct roots r1, r2: the general solution is a(n) = A·r1^n + B·r2^n.
  • One repeated root r: the general solution is a(n) = (A + B·n)·r^n.

The constants A and B are found from the starting values a(0) and a(1), which gives two equations in two unknowns.

Worked example: a(n) = 5a(n-1) - 6a(n-2), a(0) = 1, a(1) = 4. The equation r² = 5r - 6 factors as (r-2)(r-3) = 0, so the roots are 2 and 3. Then A + B = 1 and 2A + 3B = 4, which gives B = 2 and A = -1. The closed form is a(n) = 2·3^n - 2^n.

The most famous case is Fibonacci, F(n) = F(n-1) + F(n-2). Its equation r² = r + 1 has roots φ = (1 + √5)/2 and ψ = (1 - √5)/2, leading to Binet's formula F(n) = (φ^n - ψ^n)/√5. The irrational roots cancel so that every F(n) is an integer.

Higher orders work the same way: a recurrence of order k has a characteristic polynomial of degree k. If the recurrence also adds a function of n, such as a(n) = 2a(n-1) + n, you first solve the homogeneous part and then add a particular solution. That extension is beyond this lesson; unrolling works well for those cases.

Python Characteristic equations in code

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.

Floating-point arithmetic is only used here for the roots, so we round the result. For larger n, floats lose precision; exact integer methods are better when n is big, but the closed form is what shows the structure.

Divide-and-conquer and the Master theorem

Recursive algorithms often split a problem of size n into a subproblems of size n/b and spend f(n) extra work on splitting and combining. That gives a recurrence of the form

T(n) = a·T(n/b) + f(n)

Merge sort splits into 2 halves and merges in linear time: T(n) = 2T(n/2) + n. Binary search keeps one half and does constant work: T(n) = T(n/2) + 1. Unrolling reveals a tree of calls with about log_b n levels. What matters is whether the work is dominated by the leaves, the root, or is spread evenly.

The Master theorem (in its common form, with f(n) = n^d) compares a with b^d:

  • If a > b^d, the leaves dominate: T(n) = Θ(n^(log_b a)).
  • If a = b^d, every level costs the same: T(n) = Θ(n^d · log n).
  • If a < b^d, the root dominates: T(n) = Θ(n^d).

Merge sort has a = 2, b = 2, d = 1, so a = b^d and T(n) = Θ(n log n). Binary search has a = 1, b = 2, d = 0, so a = b^d and T(n) = Θ(log n). The naive recursive algorithm that makes four half-size calls with linear work, T(n) = 4T(n/2) + n, has a = 4 > 2, so it is Θ(n²).

The theorem has limits: it needs equal-size subproblems and a polynomial f(n). Recurrences like T(n) = T(n/3) + T(2n/3) + n need other tools such as recursion trees.

Python Classify and verify with the Master theorem

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.

If the classification is right, the ratio T(n)/g(n) settles near a constant as n grows. A ratio that keeps growing or shrinking tells you the guess is wrong.

Exact solutions for powers of two

For merge sort with T(1) = 0 and n = 2^k, unrolling gives exactly T(n) = n·log2 n, because there are k levels and each does n units of work. The next example confirms it and shows binary search's log2 n + 1.

Python Exact divide-and-conquer counts

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.

Which method should you use?

Start with the shape of the recurrence. If it steps back by one with a simple added term, unroll. If it is linear with constant coefficients and nothing added, use the characteristic equation. If the argument is divided, as in T(n/2), think Master theorem. Whatever you choose, finish by testing the formula on the first ten or twenty terms; later lessons on algorithm analysis rely on this habit.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. Unrolling T(n) = T(n-1) + 2 with T(0) = 5 gives which closed form?

    Each step adds 2, and there are n steps from T(0) = 5, so T(n) = 5 + 2n.
  2. 2. What are the roots of the characteristic equation for a(n) = 5a(n-1) - 6a(n-2)?

    r^2 = 5r - 6 becomes r^2 - 5r + 6 = 0, which factors as (r - 2)(r - 3), so the roots are 2 and 3.
  3. 3. The recurrence T(n) = 2T(n/2) + n has a = 2, b = 2, d = 1. What does the Master theorem give?

    Here a = b^d (2 = 2^1), so all levels of the recursion cost about the same and there are log n levels: Theta(n log n).
  4. 4. For which recurrence is the root's work dominant (a < b^d)?

    T(n) = T(n/2) + n has a = 1 and b^d = 2, so a < b^d and T(n) = Theta(n). In the others, a is larger than or equal to b^d.
  5. 5. Why should you check a closed form against the recurrence even after deriving it?

    A wrong constant or off-by-one in the derivation usually shows up within the first few terms, so a numeric test is cheap protection.

Summary

  • Solving a recurrence means finding a closed form; unrolling substitutes repeatedly until a sum or pattern appears.
  • A linear recurrence with constant coefficients is solved through its characteristic equation: distinct roots give A·r1^n + B·r2^n, a repeated root gives (A + B·n)·r^n.
  • The Master theorem handles T(n) = aT(n/b) + n^d by comparing a with b^d: leaves, all levels equally, or root.
  • Test every closed form against the recurrence for many values of n before trusting it.

Next: Counting Principles, where we start counting how many objects of a given kind exist.