The Recurrence Relations
for Janet Vassilev’s Math 327 course
Suppose we have a function f : N → R. Setting an = f (n) for all n ∈ N, we term the
set {an }∞ n=1 a sequence. Suppose we know a1 , . . . , ak and for an = f (an−1 , . . . , an−k ) for
some function f : Rk → R, we say {an }∞ n=1 is a recursively defined sequence given by the
recurrence relation an = f (an−1 , . . . , an−k ).
We say a recurrence relation is linear if f is a linear function or in other words, an =
f (an−1 , . . . , an−k ) = s1 an−1 + · · · + sk an−k + f (n) where si , f (n) are real numbers. A linear
recurrence relation is homogeneous if f (n) = 0.
The order of the recurrence relation is determined by k. We say a recurrence relation is
of order k if an = f (an−1 , . . . , an−k ). We will discuss how to solve linear recurrence relations
of orders 1 and 2.
1 Homogeneous linear recurrence relations
Let an = s1 an−1 be a first order linear recurrence relation with a1 = k. Notice, a2 = s1 k,
a3 = s1 a2 = s21 k, a4 = s1 a3 = s31 k, and in general an = ks1n−1 .
an−1 n−1
Example 1.1 If a1 = 4 and an = for n ≥ 2, then an = 4( 12 )= 1
2n−3
.
2
Suppose now that we have a homogeneous linear recurrence relation of order 2: an =
s1 an−1 + s2 an−2 with a1 = k1 and a2 = k2 . We take a guess that the solution will be of the
form an = crn . Substituting this into our recurrence relation we obtain
crn = s1 crn−1 + s2 crn−2 .
Factoring out crn−2 we obtain a quadratic equation: r2 = s1 r + s2 or
r2 − s1 r − s2 = 0.
We have three possibilities for the roots of this quadratic equation: two distinct real roots
a and b, a unique double root a or two complex conjugate roots a + ib and a − ib. The
solutions to the recurrence relation will depend on these roots of the quadratic equation.
Suppose first that the recurrence relation has two distinct real roots a and b, then the
solution of the recurrence relation will be an = c1 an + c2 bn . We use a1 = k1 and a2 = k2 to
solve the recurrence relation. Since these give us values to solve a system of equations in
two variables c1 and c2 :
k1 = c1 a + c2 b
k2 = c1 a2 + c2 b2 .
Example 1.2 Let a1 = 3 and a2 = 7 and an = 2an−1 +3an−2 for n ≥ 3. The corresponding
quadratic equation is r2 − 2r − 3 = 0 which has roots 3 and −1. So our solution should have
the form an = c1 3n + c2 (−1)n . We must now solve the system of equations
3 = 3c1 − c2
7 = 9c1 + c2 .
Adding the two equations together we obtain 10 = 12c1 or c1 = 65 . So c2 = 3( 56 ) − 3 = − 12 .
So our solution is
5 1
an = 3n − (−1)n
6 2
or
5 1
an = 3n−1 + (−1)n−1 .
2 2
If our recurrence relation has a unique double root a, then our solution will have the
form an = (c1 + c2 n)an this distinguishes us from the order one case since each quadratic
has two roots. Again we use the k1 and k2 to set up a system of equations in c1 and c2 to
find the solution of an .
Example 1.3 Let a1 = 2 and a2 = 5 and an = 6an−1 −9an−2 for n ≥ 3. The corresponding
quadratic equation is r2 − 6r + 9 = 0 which has a unique double root 3. So our solution
should have the form an = (c1 + nc2 )3n . We must now solve the system of equations
2 = 3c1 + 3c2
5 = 9c1 + 18c2 .
Subtracting 3 times the first equation from the second we obtain −1 = 9c2 or c2 = − 19 . So
c1 = 19 + 32 = 79 . So our solution is
7 1
an = 3n − n3n
9 9
or
an = 7(3n−2 ) + −n(3n−2 ).
If our recurrence relation has two complex conjugate roots, we could write our solution
the way we did in the case where we had two real roots: an = c1 (a + bi)n + c2 (a − bi)n .
However, there is a more compact √ way to write our solution in terms of real numbers. We
can write a + bi = re where r = a2 + b2 and θ = tan−1 ab . Then a − bi = re−iθ . Using
iθ
DeMoivre’s Theorem (reiθ )n = rn (cos nθ + i sin nθ). Thus
c1 (reiθ )n + c2 (re−iθ )n = rn [(c1 + c2 ) cos nθ + i(c1 − c2 ) sin nθ].
If we set C1 = c1 + c2 and C2 = i(c1 − c2 ), then our solution is
an = rn (C1 cos nθ + C2 sin nθ).
Again we can use k1 and k2 to solve a system of equations in C1 and C2 .
Example 1.4 Let a1 = 1 and a2 = 2 and an = a
√ n−1
− an−2 . The corresponding quadratic
√
equation is r − r + 1 = 0 which has roots 2 . Note that r = 1 and θ = tan−1 3 = π3 .
2 1±i 3
So our solution should have the form an = C1 cos nπ nπ
3 + C2 sin 3 . We must now solve the
system of equations √
C1 C2 3
1= +
2 2
√
C1 C2 3
2=− + .
2 2
√ √
Adding the equations together we obtain 3 = C2 3 or C2 = 3. So C1 = 2 − 3 = −1. So
our solution is
nπ √ nπ
an = − cos + 3 sin .
3 3
2 Nonhomogeneous linear recurrence relations
When f (n) 6= 0, we will search for a particular solution apn which is similar to f (n). We
will still solve the homogeneous recurrence relation setting f (n) temporarily to 0 and the
solution of this homogeneous recurrence relation will be ahn and an = apn + ahn . The following
table provides a good first guess:
f (n) apn
a0 + a1 n + · · · + ar nr b0 + b1 n + · · · + br nr
arn brn
a cos nθ + b sin nθ c cos nθ + d sin nθ
However, if the solutions to the related homogeneous recurrence relation are similar to
your function f (n) then you must multiply by an appropriate power of n. When solving
nonhomogeneous recurrence relations, you need to find the particular solution first. Then
you will solve for the needed coefficients of your related homogeneous solution using the
initial data. This will be illustrated in the examples below.
Example 2.1 Suppose an = 2an−1 − 1 for n ≥ 2 and a1 = 3. Since f (n) = −1 and
ahn = c2n , then we will guess that apn = b. We now plug this into the recurrence relation
to solve for b. Since b = 2b − 1 we see that apn = 1. Now we can solve for the c. Since
a1 = 3 = 2c + 1 we see that c = 1 and an = 2n + 1.
Example 2.2 Suppose an = 2an−1 − 2n for n ≥ 2 and a1 = 3. Since f (n) = −2n and
ahn = c2n , then we will guess that apn = bn2n . We now plug this into the recurrence relation
to solve for b. Since bn2n = 2b(n − 1)2n−1 − 2n we see that bn = b(n − 1) − 1 or b = −1.
Thus apn = −n2n . Now we can solve for the c. Since a1 = 3 = 2c − 2 we see that c = 25 and
an = 5(2n−1 ) − n2n .
Note if we did not choose our particular solution to be bn2n but b2n in the above
example, then we would get b2n = b2n − 2n or 0 = −2n and we cannot solve for b.
Example 2.3 Suppose an = 2an−1 − an−2 + 2 for n ≥ 3 with a1 = 1 and a2 = 5. Since
f (n) = 2 and ahn = c1 + c2 n, then we will guess that apn = bn2 . We now plug this into
the recurrence relation to solve for b. Since bn2 = 2b(n − 1)2 − b(n − 2)2 + 2 we see that
bn2 = 2bn2 − 4bn + 2b − bn2 + 4bn − 4b + 2 or 2b = 2 implying b = 1. Thus apn = n2 Now
we can solve for the c1 and c2 . Since a1 = 1 = c1 + c2 + 1 and a2 = 5 = c1 + 2c2 + 4, we
obtain c1 + c2 = 0 and c1 + 2c2 = 1 and see that c2 = 1 and c1 = −1 and an = −1 + n + n2 .
p
Example 2.4 Suppose an = an−1 + sin nπ 2 for n ≥ 2 and a1 = −1. We guess that an =
nπ nπ h
a sin 2 + b cos 2 since an = c. We need to solve for a and b so we plug the particular
(n−1)π
solution into the recurrence relation. a sin nπ nπ
2 + b cos 2 = a sin 2 + b cos (n−1)π
2 + sin nπ
2 .
Using the trig identities sin(A+B) = sin A cos B+sin B cos B and cos(A+B) = cos A cos B−
sin A sin B, we obtain
nπ nπ (n)π π nπ π nπ π nπ π nπ
a sin + b cos = a(sin cos( ) − cos (sin )) + b(cos cos + sin sin ) + sin
2 2 2 2 2 2 2 2 2 2 2
nπ nπ nπ
= −a cos + b sin + sin
2 2 2
.
Simplifying we get
nπ nπ nπ
(a − b) sin + (a + b) cos = sin
2 2 2
which implies that a−b = 1 and a+b = 0 so a = 12 and b = − 12 and apn = 12 sin nπ 1 nπ
2 − 2 cos 2 .
1 3
Now we solve for c using a1 = −1 and −1 = c + 2 implies that c = − 2 So
3 1 nπ 1 nπ
an = − + sin − cos .
2 2 2 2 2
