Recurrence Relations and How to Solve Them

A recurrence relation defines each term of a sequence using earlier terms, just as a recursive function calls smaller copies of itself. Recurrences appear everywhere in computer science, from counting the moves in the Tower of Hanoi to measuring the running time of merge sort. This guide shows you the three methods you will use most often, each with complete worked examples.

What Is a Recurrence Relation?

A recurrence has two parts: a rule linking a term to previous terms, and one or more initial conditions that get it started. The famous Fibonacci sequence is

$$ F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 0, \; F_1 = 1 $$

which produces 0, 1, 1, 2, 3, 5, 8, 13, ... Computing terms one by one is easy, but if you want \(F_{100}\) or a formula for the running time of an algorithm, you need a closed form: an expression for the \(n\)th term that does not depend on earlier terms. Finding it is what "solving" a recurrence means.

Method 1: Iteration (Unrolling)

Substitute the rule into itself repeatedly until a pattern appears, then sum the pattern.

Worked Example 1: The Tower of Hanoi

To move \(n\) discs from one peg to another, you move the top \(n - 1\) discs out of the way, move the largest disc, then move the \(n - 1\) discs back on top. If \(T_n\) is the minimum number of moves,

$$ T_n = 2T_{n-1} + 1, \qquad T_1 = 1 $$

Step 1: Unroll a few times.

$$ T_n = 2(2T_{n-2} + 1) + 1 = 4T_{n-2} + 2 + 1 $$

$$ T_n = 4(2T_{n-3} + 1) + 3 = 8T_{n-3} + 4 + 2 + 1 $$

Step 2: Spot the pattern after \(k\) steps:

$$ T_n = 2^k T_{n-k} + (2^{k-1} + \dots + 2 + 1) $$

Step 3: Choose \(k = n - 1\) so that \(T_{n-k} = T_1 = 1\):

$$ T_n = 2^{n-1} + (2^{n-1} - 1) = 2^n - 1 $$

Check: \(T_1 = 1\), \(T_2 = 2(1) + 1 = 3 = 2^2 - 1\), \(T_3 = 2(3) + 1 = 7 = 2^3 - 1\). The formula works. With 64 discs, as in the legend, you would need \(2^{64} - 1 \approx 1.8 \times 10^{19}\) moves; at one move per second that is over 580 billion years.

Method 2: The Characteristic Equation

This method solves linear homogeneous recurrences with constant coefficients, such as \(a_n = c_1 a_{n-1} + c_2 a_{n-2}\).

The idea is to guess \(a_n = r^n\). Substituting gives \(r^n = c_1 r^{n-1} + c_2 r^{n-2}\); dividing by \(r^{n-2}\) gives the characteristic equation

$$ r^2 - c_1 r - c_2 = 0 $$

• If it has two distinct roots \(r_1, r_2\), the general solution is \(a_n = A r_1^n + B r_2^n\).
• If it has a repeated root \(r\), the general solution is \(a_n = (A + Bn) r^n\).

The constants \(A\) and \(B\) come from the initial conditions.

Worked Example 2: Distinct Roots

Solve \(a_n = 5a_{n-1} - 6a_{n-2}\) with \(a_0 = 1\) and \(a_1 = 4\).

Step 1: Write the characteristic equation.

$$ r^2 - 5r + 6 = 0 \implies (r - 2)(r - 3) = 0 \implies r = 2 \text{ or } r = 3 $$

Step 2: General solution: \(a_n = A \cdot 2^n + B \cdot 3^n\).

Step 3: Use the initial conditions.

• \(n = 0\): \(A + B = 1\)
• \(n = 1\): \(2A + 3B = 4\)

Multiply the first equation by 2 and subtract: \(B = 4 - 2 = 2\), so \(A = 1 - 2 = -1\).

Step 4: The closed form is

$$ a_n = 2 \cdot 3^n - 2^n $$

Check: From the recurrence, \(a_2 = 5(4) - 6(1) = 14\). From the formula, \(a_2 = 2(9) - 4 = 14\). Also \(a_3 = 5(14) - 6(4) = 46\) and \(2(27) - 8 = 46\). Both agree.

Worked Example 3: Fibonacci's Closed Form

For \(F_n = F_{n-1} + F_{n-2}\), the characteristic equation is \(r^2 - r - 1 = 0\), so

$$ r = \frac{1 \pm \sqrt{5}}{2} $$

Call these \(\varphi \approx 1.618\) (the golden ratio) and \(\psi \approx -0.618\). Using \(F_0 = 0\) gives \(A + B = 0\), and \(F_1 = 1\) gives \(A\varphi + B\psi = 1\). Since \(\varphi - \psi = \sqrt{5}\), we get \(A = \frac{1}{\sqrt{5}}\) and \(B = -\frac{1}{\sqrt{5}}\):

$$ F_n = \frac{\varphi^n - \psi^n}{\sqrt{5}} $$

This is Binet's formula. Because \(|\psi| < 1\), the \(\psi^n\) term shrinks quickly, so \(F_n\) is simply \(\frac{\varphi^n}{\sqrt{5}}\) rounded to the nearest integer. For example, \(\varphi^{10} \approx 122.99\) and \(122.99 / 2.236 \approx 55.0\), and indeed \(F_{10} = 55\). It also explains why naive recursive Fibonacci code is so slow: its running time grows like \(\varphi^n\).

Method 3: The Master Theorem

Divide-and-conquer algorithms split a problem of size \(n\) into \(a\) subproblems of size \(n/b\) and do \(f(n)\) extra work to split and combine:

$$ T(n) = a\,T\!\left(\frac{n}{b}\right) + f(n) $$

Compare \(f(n)\) with \(n^{\log_b a}\). In the common case \(f(n) = \Theta(n^d)\):

• If \(d < \log_b a\): \(T(n) = \Theta(n^{\log_b a})\). The subproblems dominate.
• If \(d = \log_b a\): \(T(n) = \Theta(n^d \log n)\). Work is balanced across levels.
• If \(d > \log_b a\): \(T(n) = \Theta(n^d)\). The top-level work dominates.

Worked Example 4: Merge Sort and Others

Merge sort: \(T(n) = 2T(n/2) + n\). Here \(a = 2\), \(b = 2\), \(d = 1\), and \(\log_2 2 = 1 = d\). This is the balanced case, so \(T(n) = \Theta(n \log n)\).

Sanity check by unrolling: the recursion tree has \(\log_2 n\) levels, and each level does a total of \(n\) work merging, giving \(n \log_2 n\). For \(n = 8\) with \(T(1) = 0\): \(T(2) = 2\), \(T(4) = 2(2) + 4 = 8\), \(T(8) = 2(8) + 8 = 24 = 8 \times 3\). Correct.

Binary search: \(T(n) = T(n/2) + 1\). Here \(a = 1\), \(b = 2\), \(d = 0\), and \(\log_2 1 = 0 = d\), so \(T(n) = \Theta(\log n)\).

A heavier recursion: \(T(n) = 4T(n/2) + n\). Now \(\log_2 4 = 2 > d = 1\), so \(T(n) = \Theta(n^2)\). Splitting into four half-size problems costs more than the linear combining work.

Did You Know?

• The Tower of Hanoi puzzle was invented by the French mathematician Édouard Lucas in 1883, along with the legend of priests moving 64 golden discs.
• Fibonacci introduced his sequence in 1202 in the book Liber Abaci, through a puzzle about breeding rabbits, though the numbers were known earlier to Indian scholars studying poetic metres.
• The ratio of consecutive Fibonacci numbers approaches the golden ratio: \(\frac{89}{55} \approx 1.61818\).

Key Takeaways

• A recurrence needs both a rule and initial conditions; solving it means finding a closed form.
• Iteration (unrolling) works well for simple first-order recurrences like the Tower of Hanoi.
• Linear recurrences with constant coefficients are solved using the roots of the characteristic equation.
• The Master Theorem gives running times of divide-and-conquer algorithms by comparing \(f(n)\) with \(n^{\log_b a}\).
• Always check your closed form against a few terms computed directly from the recurrence.

If a recurrence relation or algorithm analysis question has you stuck, Amathify's experts and PhD scholars can provide step-by-step solutions and assignment help via WhatsApp or the Ask a Question form.