Discrete Math · Undergraduate

Recurrence Relations and How to Solve Them

Quick answer

A recurrence relation defines each term of a sequence from earlier terms, together with starting values: the Fibonacci numbers satisfy Fₙ = Fₙ₋₁ + Fₙ₋₂. Computing terms one by one suits a computer but is slow by hand. A linear recurrence with constant coefficients, such as aₙ = 5aₙ₋₁ − 6aₙ₋₂, has a closed form found by trying aₙ = rⁿ: the roots of the characteristic equation give the building blocks, and the starting values fix the constants.

What you'll learn

  • Compute terms of a sequence from a recurrence
  • Set up a recurrence for a counting problem
  • Solve linear recurrences with the characteristic equation
  • Handle a repeated characteristic root

Defining a sequence by its past

A recurrence relation gives each term from earlier ones. The arithmetic and geometric sequences are the simplest: an=an−1+3a_n = a_{n-1} + 3 and an=2an−1a_n = 2a_{n-1}. The Fibonacci numbers use two earlier terms:

Fn=Fn−1+Fn−2,F0=0, F1=1F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 0,\ F_1 = 1

giving 0,1,1,2,3,5,8,13,21,34,55,…0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots. A recurrence needs as many starting values as the number of earlier terms it uses.

Many counting problems lead to recurrences. In the Tower of Hanoi, nn disks must move between pegs, one at a time, never putting a larger disk on a smaller. To move nn disks, move the top n−1n - 1 aside, move the largest, then move the n−1n - 1 back on top: hn=2hn−1+1h_n = 2h_{n-1} + 1, with h1=1h_1 = 1.

The characteristic equation

A linear recurrence with constant coefficients, such as an=5an−1−6an−2a_n = 5a_{n-1} - 6a_{n-2}, can be solved in closed form. Try an=rna_n = r^n:

rn=5rn−1−6rn−2⟹r2−5r+6=0⟹r=2,3r^n = 5r^{n-1} - 6r^{n-2} \quad\Longrightarrow\quad r^2 - 5r + 6 = 0 \quad\Longrightarrow\quad r = 2, 3

Both 2n2^n and 3n3^n satisfy the recurrence, and so does any combination an=A⋅2n+B⋅3na_n = A \cdot 2^n + B \cdot 3^n. The starting values pick AA and BB.

Why combinations work

The recurrence is linear: if two sequences each satisfy it, so does any sum of multiples of them, since the recurrence only adds and scales terms. So the solutions form a two-dimensional family, and two independent solutions build all of them. This is exactly the structure of second-order differential equations, with rnr^n in place of erxe^{rx}. A repeated root needs a second solution, and as there, multiplying by nn provides it: (A+Bn)rn(A + Bn)r^n.

Worked examples

Common mistakes

Practice problems

  1. Solve an=3an−1a_n = 3a_{n-1} with a0=2a_0 = 2.

    Answer

    an=2⋅3na_n = 2 \cdot 3^n

    Full solution

    Each term triples the last: a geometric sequence.

  2. Solve an=an−1+3a_n = a_{n-1} + 3 with a0=2a_0 = 2.

    Answer

    an=3n+2a_n = 3n + 2

    Full solution

    Each term adds 33: an arithmetic sequence.

  3. Find F12F_{12}.

    Answer

    144144

    Full solution

    Continue from F10=55F_{10} = 55, F11=89F_{11} = 89: F12=89+55F_{12} = 89 + 55.

  4. Solve an=7an−1−10an−2a_n = 7a_{n-1} - 10a_{n-2} with a0=2a_0 = 2, a1=7a_1 = 7.

    Answer

    an=2n+5na_n = 2^n + 5^n

    Full solution

    r2−7r+10=(r−2)(r−5)r^2 - 7r + 10 = (r - 2)(r - 5). Then A+B=2A + B = 2 and 2A+5B=72A + 5B = 7 give A=B=1A = B = 1.

  5. How many moves does the Tower of Hanoi need for 66 disks?

    Answer

    6363

    Full solution

    26−12^6 - 1.

  6. Solve an=6an−1−9an−2a_n = 6a_{n-1} - 9a_{n-2} with a0=1a_0 = 1, a1=6a_1 = 6.

    Answer

    an=(1+n)3na_n = (1 + n)3^n

    Full solution

    (r−3)2(r - 3)^2 gives a double root. A=1A = 1 and 3(A+B)=63(A + B) = 6, so B=1B = 1.

  7. Let sns_n count binary strings of length nn with no two 11s in a row. Explain why sn=sn−1+sn−2s_n = s_{n-1} + s_{n-2}, and find s5s_5.

    Answer

    s5=13s_5 = 13

    Full solution

    A valid string ends in 00 (any valid string of length n−1n - 1, then 00) or in 0101 (any valid string of length n−2n - 2, then 0101). With s1=2s_1 = 2 and s2=3s_2 = 3: 5,8,135, 8, 13.

  8. A student solves an=4an−1−4an−2a_n = 4a_{n-1} - 4a_{n-2} as A⋅2n+B⋅2nA \cdot 2^n + B \cdot 2^n and cannot fit a0=1a_0 = 1, a1=4a_1 = 4. Why?

    Answer

    With a double root, the second solution is n2nn2^n; the form must be (A+Bn)2n(A + Bn)2^n.

    Full solution

    A⋅2n+B⋅2n=(A+B)2nA \cdot 2^n + B \cdot 2^n = (A + B)2^n has one free constant, but two starting values need two.

Frequently asked questions

What is a recurrence relation?

A rule that gives each term of a sequence from earlier terms, such as aₙ = aₙ₋₁ + 3, together with enough starting values to begin.

How do you solve aₙ = c₁aₙ₋₁ + c₂aₙ₋₂?

Try aₙ = rⁿ to get the characteristic equation r² = c₁r + c₂. With distinct roots r₁, r₂, the solution is aₙ = A·r₁ⁿ + B·r₂ⁿ, and the starting values fix A and B.

What if the characteristic equation has a repeated root?

With a double root r, the solution is aₙ = (A + Bn)rⁿ.

What is the closed form of the Tower of Hanoi?

Moving n disks takes hₙ = 2hₙ₋₁ + 1 moves, with h₁ = 1, and the closed form is hₙ = 2ⁿ − 1.

How are recurrences like differential equations?

Both describe change step by step, and linear ones with constant coefficients are solved the same way: try an exponential, solve a characteristic equation, and combine the solutions.

What to learn next