How to Find a Recurrence Relation: 5 Methods with Examples

Before you start

1. Define a_n precisely, for example “the number of valid strings of length n”.
2. Work out the first few values by hand. They reveal the pattern and give you something to check against.
3. Decide what “one step smaller” means: remove the last symbol, the last item, or half of the input.

Method 1: look at the last symbol

Count ternary strings (using 0, 1, 2) of length n that never contain two 0s in a row. Look at the last symbol of a valid string.

• If it is 1 or 2 (two choices), the first n − 1 symbols can be any valid string: 2·a(n−1) strings.
• If it is 0, the symbol before it must be 1 or 2 (two choices), and the first n − 2 symbols can be any valid string: 2·a(n−2) strings.

So a(n) = 2·a(n−1) + 2·a(n−2), with a(0) = 1 (the empty string) and a(1) = 3. The next terms are a(2) = 8, a(3) = 22, a(4) = 60. Listing the 22 valid strings of length 3 by hand confirms a(3).

Method 2: decide about the n-th item

Count the subsets of {1, 2, …, n} that contain no two consecutive numbers. Either n is not in the subset, leaving any valid subset of {1, …, n−1}, or n is in the subset, so n − 1 is not, leaving any valid subset of {1, …, n−2}.

So a(n) = a(n−1) + a(n−2), with a(0) = 1 (the empty set) and a(1) = 2. The terms are 1, 2, 3, 5, 8, 13: a Fibonacci-type sequence. For n = 3 the valid subsets are ∅, {1}, {2}, {3} and {1, 3}, which is 5.

Method 3: split by the first or last step

How many ways can you climb n stairs taking 1, 2 or 3 stairs at a time? Look at the last step. It was a 1-step from stair n − 1, a 2-step from stair n − 2, or a 3-step from stair n − 3.

So a(n) = a(n−1) + a(n−2) + a(n−3), with a(0) = 1, a(1) = 1, a(2) = 2. The terms continue 4, 7, 13, 24.

Method 4: translate a rule directly

Sometimes the problem states the rule and you only have to write it down. A savings account earns 1% interest each month and you add 100 at the end of each month, starting from 1000. If b(n) is the balance after n months, then b(n) = 1.01·b(n−1) + 100 with b(0) = 1000.

The first two balances are b(1) = 1110.00 and b(2) = 1221.10. This is a first-order linear recurrence of the form a(n) = r·a(n−1) + d, which the calculator solves in closed form.

Method 5: divide and conquer

Recursive algorithms give recurrences for their running time. Merge sort splits a list of n items into two halves, sorts each, then merges in about n steps, so T(n) = 2·T(n/2) + n. Binary search discards half the list with one comparison, so T(n) = T(n/2) + 1.

Taking T(1) = 0 and n a power of 2, merge sort gives T(2) = 2, T(4) = 8, T(8) = 24, which matches n·log₂ n. Recurrences of this shape are solved with the Master theorem or by unrolling.

How to check your recurrence

• Compute the first five or six terms from the recurrence and compare them with values you counted by hand.
• Make sure the starting values really cannot be produced by the recurrence itself. They are the base cases.
• Check that the recurrence only refers to smaller indices, so it can actually be computed.
• If you find a closed form, prove it by induction or test it against the computed terms.

Common mistakes

• Forgetting the initial conditions, or giving too few of them. A recurrence that reaches back two terms needs two starting values.
• Counting some objects twice because two cases overlap.
• Using a different meaning for a(n) halfway through. Define it once and keep it.
• Mixing up the index, for example using a(n−1) where the problem really removes two items.