New Zealand Mathematical Olympiad Committee

Recurrence relations
Chris Tuffley

1 Introduction
Have you met the Fibonacci sequence before? It starts out 1, 1, 2, 3, 5, 8, 13, . . ., and to find
the next number or term you just add the last two: so the next term here is 8 + 13 = 21.
We can write this mathematically as

fn+1 = fn + fn−1 , (1)

which says that the (n + 1)th term is the sum of the nth and (n − 1)th. An equation such
as this that tells us how to find the next term of a sequence in terms of one or more of the
preceding terms is known as a recurrence relation. Recurrence relations can come in various
flavours that are more or less difficult to solve, and the one we have here is a second order
linear homogeneous recurrence relation with constant co-efficients. That’s a bit of a mouthful,
but sometimes, the more words you use the easier something gets, and we’ll see later that such
recurrences can be solved quite easily. First, though, I’ll explain what all those terms mean.
The order of a recurrence relation tells us how far back in the sequence we have to go in order
to calculate the next term. The Fibonacci sequence depends only on the previous two terms,
so it’s second order; the recurrence

an = an−2 + an−3

is third order, because I need to go back three terms in order to find an , even though I only
use two out of three of those terms. Note that the order of a recurrence relation need not be
defined: for example, the Catalan numbers (a famous sequence that has a habit of cropping up
all over the place) satisfy the recurrence

Cn = C1 Cn−1 + C2 Cn−2 + · · · + Cn−1 C1 , (2)

in which each term depends on all of the earlier terms.

A linear recurrence relation is one which may be written in the form

an = c1 an−1 + c2 an−2 + · · · + ck an−k + bn ,

where c1 , c2 , . . . , ck , bn may be functions of n but not of the ai . Equation (2) does not have this
form, because it has terms of the form Ci Cj , so it is an example of a nonlinear recurrence. As
a general rule in mathematics, nonlinearity almost always makes things harder!
A linear recurrence is homogeneous if bn is zero for all n, and non-homogeneous otherwise. For
example, the recurrence qn = 2qn−1 + 4n−1 is non-homogeneous, with non-homogeneous term

1
4n−1 . Finally, a linear recurrence relation has constant co-efficients if the ci are independent
of n. The linear recurrence relations given so far all satisfy this condition (note that for this
purpose we don’t care about the non-homogeneous term); an example of one that has non-
constant co-efficients is the recurrence Dn = (n − 1)(Dn−1 + Dn−2 ), which is satisfied by the
derangement numbers. Unfortunately, the method for solving linear recurrence relations that
we’ll give below only applies to the constant co-efficient case.
Before we move on to finding and solving recurrence relations, a few more words are needed.
A recurrence relation only tells us how to find the next term of the sequence; it doesn’t tell us
how to start things off. To pin the sequence down completely we must also specify the initial
conditions. For example, the Fibonacci sequence is defined by the recurrence (1), together with
the initial conditions f0 = f1 = 1. If we use the same recurrence ln = ln−1 + ln−2 with the initial
conditions l0 = 2, l1 = 1 we get the Lucas numbers instead.
In general, for a kth order recurrence the initial conditions must specify the first k terms.

2 Finding a recurrence relation

We’ll illustrate the kinds of ideas used in finding a recurrence relation by looking at several
examples. But first, a little language. You can probably guess what a binary sequence of length
n is: it’s a sequence of n 0s and 1s. Similarly, a ternary sequence is a sequence of 0s, 1s and
2s, and a quaternary sequence is a sequence of 0s, 1s, 2s and 3s.
Example 1. Let tn be the number of ternary sequences of length n that do not have any non-zero
terms adjacent. Find a recurrence relation and initial conditions for tn .

Solution: Clearly t1 = 3, and t2 = 5. To find t3 , we might start listing the sequences by their
first digit. If this is 0, it can be followed by any of the five sequences of length two; but if it
is 1 or 2, it must be followed by a 0, and then by any of the three sequences of length 1. So
t3 = 5 + 2 × 3 = 11. Hey! This idea works just as well for n larger than three: if the first digit
is 0, the rest can be any of the tn−1 allowable sequence of length n − 1; and if it’s 1 or 2, it
must be followed by 0, and then by any of the tn−2 allowable sequences of length n − 2. So the
recurrence we’re looking for must be
tn = tn−1 + 2tn−2 .
This is second order, so we need two consecutive values as initial conditions, which we’ve already
found above.
Before moving on, let’s see if we can make sense of t0 , as it’s sometimes convenient (but usually
not essential) to use this as one of our initial conditions. This should count the number of
ternary sequences of length zero with no nonzero entries adjacent. Well, there’s only one ternary
sequence of length zero—the empty sequence, “ ”—and it doesn’t have any nonzero terms
adjacent, so t0 must be 1. This fits with what we found above, because t1 +2t0 = 3+2 = 5 = t2 ,
so we could instead take t0 = 1, t1 = 3 as our initial conditions.
Example 2. Let qn be the number of quaternary sequences of length n with an odd number of
zeros. Find a recurrence relation and initial conditions for qn .

2
Solution: Working out the first few terms we find q0 = 0 (the empty sequence has no zeros,
and so an even rather than an odd number of them), q1 = 1, and q2 = 6. To find a recurrence,
consider the first term of the sequence. If this is non-zero, the rest of the sequence must be
a quaternary sequence of length n − 1 with an odd number of zeros, of which there are qn−1 .
Altogther we get 3qn−1 sequences that start with 1, 2 or 3. On the other hand, if a sequence
starts with 0, the remaining n − 1 terms must include an even number of zeros. There are
4n−1 − qn−1 such sequences (why?), so altogether we get
qn = 3qn−1 + (4n−1 − qn−1 ) = 2qn−1 + 4n−1 .
This is first order, so the initial condition q0 = 0 is enough. Note also that it is a non-
homogeneous recurrence (in fact, it is the example of such given above).
Example 3. Find a recurrence relation for Dn , the number of derangements of n objects.

Solution: Recall that a derangement of 1 to n is a permutation of 1 to n in which no number

is in its correct position. To find a recurrence for Dn , consider where 1 ends up. It can’t end
up in the first position, leaving the n − 1 possibilities second, third, . . . , nth place. Suppose for
the moment it ended up in the second position, and consider where 2 went to. If it happened to
go to the first position, what’s left must be a derangement of 3 to n, of which there are Dn−2 ;
and if it didn’t, we can treat the permutation as a derangement of 2 to n (why?). Altogether,
this gives Dn−1 + Dn−2 derangements in which 1 is in the second position. Applying the same
argument to the remaining n − 2 positions 1 could go to we get
Dn = (n − 1)(Dn−1 + Dn−2 ).

A word of caution. When finding a recurrence relation, some care is required to make sure that
you’ve counted each thing once and once only.

3 Solving linear recurrence relations with constant co-

efficients
We’ll look first at homogeneous recurrences. Not only are they simpler, but it turns out we’ll
need to know how to solve them in order to handle the non-homogeneous case too. Note that
we cannot reasonably expect to be able to solve all non-homogeneous recurrence relations—the
non-homogeneous term could be very complicated!—but we will be able to give a complete
solution in the homogeneous case, and a method that will handle many non-homogeneous
recurrences.

3.1 The homogeneous case

If the recurrence is first order, the solution is easily found by inspection: the solution to
an = ran−1 is clearly an = a0 rn . We’ll use this as inspiration in solving higher order recurrences.
The second order case contains all the important ideas, so we’ll concentrate on that and just
say a few words at the end about third and higher order recurrences.

3
3.1.1 Second order recurrence relations

Consider the recurrence relation

an = pan−1 + qan−2 , (3)
where p and q are constants. Having nothing more to go on than the solution to the first order
recurrence found above, let’s take a stab at the solution and guess that there’s one of the form
an = αn . There certainly will be if q happens to equal 0. . . so perhaps it’s not such a stretch.
To find out what α could be we substitute our guess at the solution into the recurrence, to get

αn = pαn−1 + qαn−2 .

After dividing through by αn−2 , this tells us that αn is a solution to the recurrence if and only
if α is a root of the quadratic
α2 − pα − q = 0. (4)
This equation is called the characteristic equation of the recurrence, and the quadratic appear-
ing on the left-hand side is called the characteristic polynomial. Since quadratics typically have
two roots we will typically get two solutions of equation (3), α1n and α2n .
To continue we’ll make use of the following lemma, which tells us that as soon as we’ve found
one solution to a linear problem, we’ve found many. This is what makes linear problems so
much easier than nonlinear ones. I’ll leave you to check the details, by substituting the alleged
solution into the recurrence relation.
Lemma 1. If a0n and a00n are two solutions to a homogeneous linear recurrence relation, then so
is an = ca0n + da00n for any constants c, d.

By the lemma, when the characteristic equation has distinct roots α1 and α2 , c1 α1n + c2 α2n is a
solution to (3) for any constants c1 , c2 . This is good: the initial conditions have two degrees of
freedom (a0 and a1 can be chosen arbitrarily), so our solution will have to have two degrees of
freedom as well if we’re to have any hope of satisfying any choice of initial conditions thrown
at us. Things don’t look so rosy, however, when (4) has only a single root α0 . In this case
the lemma only gives us the solution an = cα0n , which isn’t going to cut it: we need another
solution if we want to be able to meet all possible initial conditions. Fortunately, it turns out
that when α0 is repeated, nα0n is the second solution we need. The complete solution is thus
given by the following theorem.
Theorem 2. Suppose that the characteristic equation (4) has distinct roots α1 and α2 . Then
the solution to the recurrence relation (3) is

an = c1 α1n + c2 α2n ,

where c1 and c2 are constants that may be found using the initial conditions.
If the characteristic equation has a repeated root α0 , then the solution to (3) is

an = (c1 + c2 n)α0n ,

where c1 and c2 are again constants found using the initial conditions.

4
Exercise 1. When the characteristic equation has a repeated root α = α0 , verify that nα0n is
a solution to the recurrence.
Hint: You’ll need to use the fact that α2 − pα − q = (α − α0 )2 = α2 − 2α0 − α02 .
Example 4 (Example 1, continued). Recall that tn satisfies tn = tn−1 + 2tn−2 , t0 = 1, t1 = 3.
The characteristic equation is α2 − α − 2 = (α − 2)(α + 1) = 0, so the general solution is
tn = c1 2n + c2 (−1)n .
To find c1 and c2 we substitute n = 0 and 1, to get
c1 + c2 = 1,
2c2 − c2 = 3,
and we solve these equations simultaneously to get c1 = 4/3, c2 = −1/3. The solution is
therefore tn = (4(2n ) − (−1)n )/3, which you can check gives the correct values for the next few
terms of the sequence.

3.1.2 Higher order recurrence relations

The method used above may be applied to higher order recurrence relations. If the recurrence
relation has order k, then the characteristic polynomial will be of degree k. This will typically
have k roots α1 , . . . , αk , so we will typically get k “independent” solutions to the recurrence
relation, and a general solution of the form
an = c1 α1n + · · · + ck αkn .
This expression contains k constants c1 , . . . , ck , which will allow us to satisfy any possible choice
of initial conditions a0 , . . . , ak−1 . Of course, finding the roots αi in the first place will be much
harder now!
If one of the roots αi is repeated, then we will again need to find some additional solutions to
the recurrence relation if we want to be able to meet any choice of initial conditions. It turns
out that if αi is a root of multiplicity m (this means that (α − αi )m divides the characteristic
polynomial), then αin , nαin , n2 αin , . . . , nm−1 αin are the extra solutions we need.

3.1.3 A word on roots of polynomials

You may have been taught at school that not every polynomial of degree k has k roots. If so,
you’re probably wondering how we would solve a recurrence relation such as an = 2an−1 −2an−2 :
the characteristic equation can be written (α − 1)2 = −1, which has no real root.
The answer is to allow the roots to be complex numbers, rather than restrict ourselves to
using real numbers only. If we use complex numbers, the Fundamental Theorem of Algebra
guarantees that every polynomial of degree k has exactly k roots, provided you count them
“with multiplicity”. This means that the method given above works in all possible cases—in
the example above where it appears to fail, the roots are α = 1 ± i, and the general solution is
an = c1 (1 + i)n + c2 (1 − i)n . The real difficulty lies in finding the roots in the first place, which
will generally get much harder as the degree of the polynomial goes up!

5
3.2 Non-homogeneous linear equations
Non-homogeneous linear equations can sometimes be solved using the “Method of Undeter-
mined Co-efficients”. This is really just a fancy way of saying “educated guess and check”. To
keep things simple, I’ll assume we’re trying to solve an equation of the form

an = pan−1 + qan−2 + bn , (5)

where p and q are constants, and bn is a function of n. The method I’ll explain works when bn
is an exponential (e.g. bn = 3n ), a polynomial (e.g. bn = n2 + 1), or a combination of these, and
a few other situations besides.
The key here is that if a0n and a00n are two solutions to (5), then their difference a0n − a00n is
a solution to the homogeneous recurrence (3) (check this!). This means that we can try to
solve (5) by

1. finding the general solution c1 α1n + c2 α2n to the “associated homogeneous equation” (3),
as above;

2. finding a single solution βn to the non-homogeneous equation (this is usually called a

“particular solution”);

3. adding the two to get

an = c1 α1n + c2 α2n + βn
(or αn = (c1 + c2 n)α0n + βn , in the repeated root case).

The step we don’t yet know how to do is obviously the second one. The idea behind the
Method of Undetermined Co-efficients is to guess that this will have roughly the same form as
the non-homogeneous term bn . The “roughly” part will be expressed in terms of some un-known
co-efficients that we will solve for (or determine) in order to arrive at the solution we want.
This is best illustrated through examples, so I’ll do three and leave it at that.
Example 5. Find the general solution to the recurrence an = an−1 + 2an−2 + n.

Solution: Here the non-homogeneous term is a polynomial of degree 1, so we will guess that
there is a particular solution that is also a degree one polynomial, namely an = βn = An + B.
Substituting this into the recurrence an = an−1 + 2an−2 + n gives

An + B = (A(n − 1) + B) + 2(A(n − 2) + B) + n,

or
−2An + (5A − 2B) = n.
Matching co-efficients on each side we get −2A = 1 and 5A − 2B = 0, or A = −1/2, B = −5/4.
Using the general solution to the associated homogeneous equation found in Example 4, the
general solution is
an = c1 2n + c2 (−1)n − n/2 − 5/4.

6
Note: Had we guessed only an = An instead of An + B, we’d have wound up with the unsatis-
fiable equation −2An + 5A = n. This is often a sign that something is missing from your guess;
in this case, the 5A suggests we should include a constant term B, as we did above, in order
to cancel it out. As a general rule, if the non-homogeneous term is a polynomial of degree n,
then your guess for the particular solution should be too.
Example 6 (Example 2, cont’d). Solve qn = 2qn−1 + 4n−1 , q0 = 0.

Solution: The non-homogeneous term is a multiple of 4n , so we will guess that the particular
solution is too, and try qn = βn = A4n . Substituting, we get

A4n = 2A4n−1 + 4n−1 = (2A + 1)4n−1 ,

or 4A = 2A + 1. This gives A = 1/2. The homogeneous recurrence qn = 2qn−1 has solution

qn = c2n , so the general solution is

qn = c2n + 4n /2.

Using the initial condition q0 = 0 we finally get qn = (4n − 2n )/2, which gives q1 = 1, q2 = 6,
as found above.

Example 7. Find a particular solution to the recurrence an = an−1 + 6an−2 + 3n .

Solution: As a first guess, let’s try an = βn = A3n . Substituting, we get

an = A3n = A3n−1 + 6A3n−2 + 3n = (A + 2A + 1)3n−1 .

This leads to A3n = (3A + 1)3n−1 , or 3n−1 = 0. That’s no good! The problem here is that 3n is
in fact a solution to the associated non-homogeneous equation: the characteristic polynomial
is α2 − α − 6 = (α − 3)(α + 2). When this happens, the trick is to try multiplying your guess
by n, so let’s try βn = An3n .

an = An3n = A(n − 1)3n−1 + 6A(n − 2)3n−2 + 3n = (3An − 5A + 3)3n−1 .

Now we have 3n = 5A3n−1 , which leads to the particular solution βn = 3n+1 n/5.
By now you’ll have grasped the underlying idea, and also seen some of the dodges used to avoid
some of the pitfalls that can crop up. It may all seem a little ad hoc, and so perhaps a little
unsatisfying, but it often works, so it’s worth having in your bag of tricks.

4 Problems
1. Write down the first five terms of each recurrence relation, and then find the solution.

(a) an = 5an−1 − 6an−2 , a0 = 1, a1 = 5.

(b) an = 6an−1 − 9an−2 , a0 = 1, a1 = 2.

7
 2. Find a closed formula for the nth Fibonacci number.
√
Use it to show that the ratio fn+1 /fn
1+ 5
of successive Fibonacci numbers approaches 2 (the golden ratio) as n → ∞.

3. How many ways are there to tile a 2 × n rectangle using 1 × 2 and 2 × 2 tiles, if the 1 × 2
tiles come in three colours but the 2 × 2 tiles only come in one? The 1 × 2 tiles may be
placed either horizontally or vertically.

4. Let sn be the number of ternary sequences of length n that do not contain two consecutive
0s or two consecutive 1s. Find a formula for sn by finding and solving a second order
linear recurrence relation.
Hint: If the recurrence you initially write down isn’t second order, you may have to ma-
nipulate it until it is. Once you’ve done this, try re-deriving your second order recurrence
directly.

5. Let rn be the number of ways a 1 × n rectangle may be tiled using 1 × 1, 1 × 2, and

1 × 3 rectangles, if consecutive 1 × 1 rectangles are not permitted. Find but do not solve
a recurrence relation and initial conditions for the sequence r0 , r1 , r2 , r3 , . . ..

6. Solve the given non-homogeneous recurrence relations using the method of undetermined
co-efficients.
(a) an = 4an−1 + 3 · 2n , a0 = 1.
(b) an = 6an−1 − 9an−2 + 2n, a0 = 1, a1 = 0.

7. Determine the number of ternary sequences of length n that contain the subsequence 00.

8. How many ternary sequences have no 1 anywhere to the right of a 0?

9. Find a recurrence relation and initial conditions for the number of ways of dividing 2n
people into n 2-person committees.
The number of committees can also be found directly, using standard counting techniques.
Try doing it both ways, and check that your answers agree.

10. (a) Use the recurrence relation Dn = (n−1)(Dn−1 +Dn−2 ) to show that the derangement
numbers also satisfy the first order non-homogeneous recurrence relation
Dn = nDn−1 + (−1)n .
n
X (−1)k
(b) Show by induction that Dn = n! .
k=0
k!

27th January 2009

http://www.mathsolympiad.org.nz