Recurrence Relations

Discrete Mathematics

WSB Merito University in Warsaw

Instructor: Dr. Mariusz Popieluch

Contents
1 Introduction to Recurrence Relations 2
1.1 Topics Covered . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 What Are Recurrences? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Recurrence Relations 2

3 Recursive Denitions 3

4 The Towers of Hanoi 4

4.1 Recurrence Relation for the Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . 4

5 Sorting 2n Dierent Integers by Merging: Merge Sort 6

6 Binary Search 6

7 Counting Words Without Consecutive Letters 7

7.1 A More Dicult Example (or Maybe Not So Dicult?) . . . . . . . . . . . . . . 7

8 Explicit Formula and the Iterative Method 8

8.1 Finding the Explicit Form of a Recurrence Equation by the Iterative Method . . 8

9 Divide and Conquer Paradigm and the Substitution Method 9

10 Linear Homogeneous Recurrence Equations with Constant Coecients 10

10.1 Case 1: Two Roots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
10.2 Case 2: One Root . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1
1 Introduction to Recurrence Relations
1.1 Topics Covered
ˆ Introduction

ˆ Recursive denitions, recurrence equations

ˆ Recursive thinking  nding recurrence relations for:

 Parameters of processes and algorithms

 Properties of sequences and sets

ˆ Solving recurrence relations (equations)  nding explicit formulas

 Explicit form (closed form)

 Iterative method

 Characteristic equation method

 Generating function method

1.2 What Are Recurrences?

Recurrences are a powerful tool that permeates many aspects of computer science and discrete
mathematics. We will soon discover that solutions to many programming problems, such as
sorting, searching, and even optimization algorithms, are based on recursive structures and
relations.
What is recursion? It is a technique in which the solution to a problem depends on solutions
to its smaller subproblems. In computer science, we often encounter programs or algorithms
that call themselves  and in this way break down a complicated problem into easier-to-solve
fragments. For example, recursive sorting algorithms, like quicksort or merge sort, divide a data
set into increasingly smaller parts, until individual fragments are so simple that sorting them is
trivial.
But recursion is not just about algorithms  it is also mathematics. In discrete mathematics,
recurrence relations allow us to model many problems, from counting subsets, through popula-
tion growth, to algorithm analysis. One of our main goals will be to understand how to write
such relations and how to nd their solutions using various methods.

2 Recurrence Relations
Denition 2.1 (Recurrence Relation). A recurrence relation is an equation that expresses each
element of a sequence as a function of previous elements. More precisely, in the case where only
the immediately preceding element is considered, the recurrence relation has the form:

an = φ(n, an−1 ) for n > 0,

where φ : N×X → X is a function, and X is the set to which the elements of the sequence belong.
For any a0 ∈ X , this denition uniquely determines a sequence with a0 as its rst element, called
the initial value (initial condition, or boundary condition). This denes a rst-order recurrence
relation.

Example 2.1. an = 2an−1 + 3n, a0 = 1, where φ : N × N → N.

a1 = 2 + 3 = 5, a2 = 10 + 6 = 16, . . .

2
Example 2.2 (Factorial Sequence). The factorial sequence: 1, 1, 2, 6, 24, 120, 720, . . . can be
dened recursively as follows:
(P) S0 = 1 (initial/boundary condition)
(R) Sn = n · Sn−1 for n∈N (recurrence equation)

It is easy to modify this denition to obtain sequences starting from a term with an index
higher than 1. A recurrence relation of order k has the form:

an = φ(n, an−1 , an−2 , . . . , an−k ) for n ≥ k,

where φ : N × X k → X is a function that takes into account k consecutive elements of the

sequence. In this case, k initial values are needed to dene the sequence.

Example 2.3. an = 3nan−1 + 5an−2 − 2an−3 + 7n2 an−4 − n3 ,

a0 = 0, a1 = 1, a2 = 1, a3 = 2, where φ : N × N4 → N.
Example 2.4 (Fibonacci Sequence). The Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, . . .
(P) F0 = F1 = 1 (initial conditions)
(R) Fn = Fn−1 + Fn−2 (recurrence equation)

Example 2.5 (Linear Nonhomogeneous Recurrence Equations). Linear nonhomogeneous recur-

rence equations have the following form:

xn = c1 xn−1 + c2 xn−2 + · · · + ck xn−k + f (n) + b

where c1 , c2 , . . . , ck are real numbers, f (n) is a function of n independent of earlier terms of the
sequence, and b is a constant term. In our lecture, we will mainly focus on linear nonhomogeneous
recurrence equations of the rst order and homogeneous equations of the second order with
constant coecients.

3 Recursive Denitions
We say that a sequence of terms (e.g., symbols, numbers, sets, structures, processes) is dened
recursively if:

(P) A certain nite set of terms of the sequence is specied, usually the rst few terms or the
rst term.

(R) The remaining terms of the sequence are dened using previous terms of the sequence.

The formula dening the sequence in this way is called a recursive formula, recurrence equa-
tion, or recurrence relation. Condition (P) contains the base or initial step of the denition.
The remaining terms of the sequence are determined successively using rule (R).
The examples of recurrence relations given above satisfy these conditions, so they are recur-
sive denitions of sequences of elements from any set.
Not only sequences can be dened recursively, but also sets (where the order of terms is not
important, only the content of the set). In this case, we have one initial condition and several
recursive conditions, as well as a closure condition.

Example 3.1 (Set of All Formulas in Classical Propositional Logic). The set of all formulas
(For) in classical propositional logic is dened as follows:
P Propositional variables are formulas: p, q, r, . . . ∈ For.
R.1 If α ∈ For, then ∼ α ∈ For.
R.2 If α, β ∈ For, then (α → β) ∈ For.
R.3 If α, β ∈ For, then (α ∨ β) ∈ For.

3
 R.4 If α, β ∈ For, then (α ∧ β) ∈ For.
R.5 If α, β ∈ For, then (α ≡ β) ∈ For.
T Every formula in classical propositional logic is built from propositional variables, connec-
tives, and parentheses according to the rules specied in points P, R.1R.5.

The closure condition T is needed for the above denition because all conditions in this
denition are merely sucient conditions, so we must add that nothing other than formulas
admitted in these conditions is included in the set For. We could formulate this denition
dierently, and then the closure condition would not be needed.

4 The Towers of Hanoi

Example 4.1 (The Towers of Hanoi Problem). The Towers of Hanoi is a problem involving
reconstructing, while preserving the shape, a tower of disks with dierent diameters (a popular
puzzle), where during the transfer one may use a buer (represented in this case by an additional
peg), but with the general assumption that one may not place a disk with a larger diameter
on a smaller one, nor transfer several disks at once. This is an example of a problem whose
computational complexity grows extremely rapidly as the input parameter increases, i.e., the
number of elements in the tower.
The question is: how many moves are needed to transfer 64 disks?
History of the puzzle: The Towers of Hanoi puzzle probably originated in East Asia in
the 19th century or earlier. The disks were ceramic, produced in China, Japan, and Vietnam.
This game was rst brought to the West by French mathematician Édouard Lucas in 1883. A
Tibetan legend was attached to the sold set, according to which monks in the temple of Brahma
are solving this puzzle with 64 golden disks.
The legend says that when the monks complete the task, the end of the world will come.
Assuming they make 1 move per second, arranging the tower will take 18,446,744,073,709,551,615
(nearly 18 and a half quintillion) seconds, or about 584.6 billion years!

4.1 Recurrence Relation for the Towers of Hanoi

The recurrence equation determining the minimum number of moves Rn needed to solve the
Towers of Hanoi problem for n disks:

R1 = 1
Rn = 2Rn−1 + 1

Proof. It suces to notice that to move all n disks, one must rst transfer n − 1 disks to
free the bottom disk, i.e., perform as many moves as were needed to transfer n − 1 disks, i.e.,
Rn−1 . Then one must move the bottom disk (1 move) and again transfer n − 1 disks onto this
largest disk, i.e., again Rn−1 moves.
Recursive thinking: It suces to assume that the term (value) of the sequence an−1
is known and only need to appropriately express an under this assumption. (The inductive
hypothesis in mathematical induction works similarly.)
Calculating some sets may turn out to be dicult, and even quite laborious by combinatorial
methods (which we will learn soon), but very simple if the given set can be dened recursively,
after which a machine can do it for us.
One cannot discuss recurrence relations without discussing the famous Fibonacci sequence
and where it comes from.

Example 4.2 (Rabbit Counting Problem  The Genesis of the Fibonacci Sequence). Let us
imagine a rabbit farm in which we study the rate of population growth. The problem is to

4
estimate how many pairs of rabbits we will have after a certain time (n months), assuming
certain simplied conditions:
At the beginning, we have one pair of young rabbits. Each pair of rabbits becomes fertile
only after one month from birth. This means that in the month of birth and the rst month
of life, a pair cannot reproduce. For simplicity, we assume that rabbits are born at the very
beginning of the month, so they reproduce for the rst time only at the beginning of the second
month after birth. Moreover, each fertile pair gives birth to exactly one new pair of rabbits
per month. Rabbits do not die, so their number can only grow. We want to nd a recurrence
relation for the number of rabbit pairs at the beginning of the n-th month, Fn .
Let us deduce how many pairs of rabbits there should be in the rst few months.

F0 = 1 Just after birth, the rst pair is infertile, so the sum

of all pairs is only this one, newborn pair.

F1 = 1 At the beginning of the rst month after birth, the rst pair

is still infertile, so the sum of all pairs is still only

this one, infertile pair.

F2 = 2 At the beginning of the second month, the rst pair gives birth

for the rst time to one pair, which of course is still

infertile just after birth.

So how many pairs of rabbits will there be at the beginning of the n-th month? Let's think
recursively!
In this model, by assumption, rabbits do not die, so all pairs that were already alive in the
previous month will also be alive in the next month. So at the beginning of the n-th month
there will be at least Fn−1 pairs of rabbits. But that's not all. Each pair of rabbits that is at
least two months old, i.e., a total of Fn−2 pairs, will reproduce at the beginning of the n-th
month. So this justies the relation:

Fn = Fn−1 + Fn−2

Alternatively, we can reason as follows: Rabbits do not die, so at the beginning of the n-th
month there will be at least Fn−1 pairs of rabbits (i.e., the same as in the previous month). And
now let's assume that each of these pairs reproduces in the n-th month, which in total gives
Fn = 2Fn−1 . But in this calculation, we also assumed that X pairs of rabbits that were born in
the previous month will reproduce already at the beginning of the n-th, which is false because
they are one month too young. Since we counted X too many, Fn should equal 2Fn−1 − X .
And what is X? These are pairs that did not yet exist two months ago and were born only at
the beginning of the previous month. Therefore, there are X = Fn−1 − Fn−2 pairs. So at the
beginning of the n-th month there are 2Fn−1 − (Fn−1 − Fn−2 ) pairs.
And of course, 2Fn−1 − (Fn−1 − Fn−2 ) = Fn−1 + Fn−2 .

Exercise 4.1. In how many ways sn can one climb stairs built of n steps, if in each step one
can overcome 1 or 2 steps? Give a recursive formula for sn .
Hint: think recursively!
Exercise 4.2. For a grid of m×n squares, give a recursive formula for the number of all paths
from the upper-left corner square A, i.e., (1, 1) to the lower-right corner square B, i.e., (m, n),
for m, n ≥ 1, if one can only move right or down.
Hint: think recursively, and it is worth considering two cases where from square A the rst
step is down or to the left.

5
5 Sorting 2n Dierent Integers by Merging: Merge Sort
Let us rst solve the problem of so-called merge sort. We have 2n dierent integers. Our task
will be to arrange all numbers in order from largest to smallest. We will do this as follows. First,
we divide the set of numbers into two parts of 2n−1 numbers each.
Next, we order each of these parts, similarly, from largest to smallest. Then we compare
the largest numbers from both parts and set aside the larger one as the largest of all. Then we
compare the largest numbers from both parts (one of these parts is now smaller, because one
number has been removed from it). We set aside the larger number as the second in order. And
so on.
We still need to explain how we order both parts. Well, we will do it in the same way. We
divide each of these parts again into two parts, order them, and then merge them together. We
order each of these smaller parts again in the same way: we divide into two parts and then
merge them together. And so on.
Finally, we will reach parts containing only two numbers, and then one comparison is enough
to order such a small part. How many comparisons are needed to order all numbers in a set of
2n numbers using this method? We are talking about the maximum number of comparisons 
we do not assume that we will be lucky (example*) with the initial unordered distribution of
numbers.
*Example: Suppose the set {1, 2, 3, 4, 5, 6, 7, 8} is already partially ordered. We have two
parts of 4 numbers each, where all are ordered relative to each other.

Ideal (lucky) arrangement Intermediate arrangement Worst arrangement

Part 1 1,2,3,4 1,2,3,8 1,3,5,7
Part 2 5,6,7,8 4,5,6,7 2,4,6,8

Analysis: In the ideal ordering, we make only 4 comparisons to order all 8 elements. In
the worst case, we must make 7 = 2·4−1 comparisons (i.e., in our general case 2 · 2n−1 − 1
comparisons (−1 because the last remaining number no longer needs to be compared  it is
known to be the smallest)). In the example intermediate case, we make 5 comparisons.

Pn = 2Pn−1 + 2 · 2n−1 − 1 = 2Pn−1 + 2n − 1

6 Binary Search
Example 6.1 (Binary Search). We are searching for the 5th element on the list, i.e., the name
Emilia.
Step 1: ⌊8/2⌋ = 4 (fourth element) <5
so we continue searching on the section of the list 58, ignoring the part of the list 14.
Step 2: ⌊4/2⌋ = 2 (sixth element) >5
so we continue searching on the section of the list 56, ignoring the part of the list 78.
Step 3: ⌊2/2⌋ = 1 (fth element) =5
End.

Example 6.2 (Searching an Ordered List of Length 2k , k ∈ N: Binary Search). Recursive

formula for the maximum number of comparisons:

P2n = Pn + 1 or Pn = Pn/2 + 1

Initial term: In the case of one element, we make 0 comparisons.

P1 = 0

6
7 Counting Words Without Consecutive Letters
Example 7.1. Let Σ = {a, b, c}. We are interested in the number sn of words of length n in
which two consecutive letters a do not appear, i.e., those that do not contain the string aa. We
want to nd a recurrence equation for sn .
Solution: Let Bn be the set of words in Σn in which the string aa does not appear, and let
sn denote the number of words in Bn .
Then, B0 = {λ}, B1 = {a, b, c}, B2 = {bb, bc, cb, cc, ab, ba, ac, ca}. Therefore s0 = 1, s1 = 3,
s2 = 9 − 1 = 8.
n
If a word in Σ ends with b, it can be preceded by any word from Bn−1 . Therefore sn−1
words in Bn end with the letter b. Similarly, sn−1 words in Bn end with the letter c. Therefore
2sn−1 words in Bn end with the symbol b or c.
And how many words in Bn end with the letter a? If a word in Bn ends with the letter a, it
must be preceded by a word from Σ
n−1 that does not end with the letter a. That is, it must be

preceded by a word from Bn−1 that ends with b or c. How many such words are there? These
are all words from Bn−2 , with the letter b or c added in the n − 1 position. So there are 2sn−2
of them:
sn = 2sn−1 + 2sn−2
Alternatively, we can reason as follows. We assume that there are 3sn−1 words satisfying
the condition. That is, any word from Bn−1 ending with the letters a or b or c. Only in this
calculation we also included words from Bn−1 that end with the letter a, which is not allowed 
we do not want to count these sequences. And how many are there? The reasoning is similar to
the previous version: words in Bn−1 ending with a are as many as words from Bn−2 not ending
with a  i.e., ending with b orc, i.e., as many as words from Bn−3 with the letter b or c added
in the n−2 position, which totals 2sn−3 . So from this it follows that:

sn = 3sn−1 − 2sn−3

We can check the consistency of the rst few terms of the sequence sn in both versions, but
to be sure we would have to solve the recurrences, nding an explicit formula and make sure
that it is the same for both formulas. Here are the rst few terms:

Formula one Formula two

s3 2(3 + 8) = 22 3 · 8 − 2 · 1 = 22
s4 2(8 + 22) = 60 3 · 22 − 2 · 3 = 60
s5 2(60 + 22) = 164 3 · 60 − 2 · 8 = 164
s6 2(164 + 60) = 448 3 · 164 − 2 · 22 = 448

7.1 A More Dicult Example (or Maybe Not So Dicult?)

Example 7.2. Find a recurrence equation for the number of words tn over a three-letter alphabet
Σ = {a, b, c} of length n containing an even number of the symbol a.
Solution: Let Bn be the set of words in Σn a
in which an even number of the symbol
appears, and let tn denote the number of words in Bn .
Then, B0 = {λ}, B1 = {b, c}, B2 = {aa, bb, bc, cb, cc}. Therefore t0 = 1, t1 = 2, t2 = 5. We
count the number of words in Bn by looking at the last letter.
n
If a word in Σ ends with b, it can be preceded by any word from Bn−1 . Therefore tn−1
words in Bn end with the letter b. Similarly, tn−1 words in Bn end with the letter c. Therefore
2tn−1 words in Bn end with the symbol b or c.
If a word in Bn ends with the letter a, it must be preceded by a word from Σ
n−1 in which

there is an odd number of letters a. Since Σ

n−1 has 3
n−1 words, then 3
n−1 − tn−1 of them must
have an odd number of letters a. Hence 3
n−1 − t words in B end with the letter a.
n−1 n

7
 Therefore,
tn = 2tn−1 + (3n−1 − tn−1 ) = 3n−1 + tn−1
for n ≥ 1.
Hence t3 = 32 + t2 = 9 + 5 = 14, t4 = 33 + t3 = 27 + 14 = 41, etc.

8 Explicit Formula and the Iterative Method

In recurrence theory, an important problem is solving a recurrence relation in explicit form, i.e.,
obtaining an expression in which the sought value R(n) depends only on n. One of the methods
for establishing an explicit form is called the iterative method.

Example 8.1 (Explicit Form of a Recurrence Relation). Arithmetic and geometric sequences.
A numerical sequence (an ) is called an arithmetic sequence if for some number r (called
the common dierence of the sequence) the following holds (∀n ≥ 1):
an+1 = an + r
Recurrence relation:
Explicit form: an+1 = a1 + nr
A numerical sequence (an ) is called a geometric sequence if there exists a constant q called
the common ratio of the sequence, for which the following formula holds (∀n ≥ 1):
Recurrence relation: an+1 = qan
n
Explicit form: an+1 = q a1

8.1 Finding the Explicit Form of a Recurrence Equation by the Iterative

Method
Solving this recurrence for the Towers of Hanoi, i.e., nding an explicit formula for Rn by the
iterative method, looks as follows:

Rn = 2Rn−1 + 1
R1 = 1
R2 = 2 · 1 + 1 = 21 + 1
R3 = 2 · (2 + 1) + 1 = 22 + 2 + 1
R4 = 2 · (22 + 2 + 1) + 1 = 23 + 22 + 2 + 1
R5 = 2 · (23 + 22 + 2 + 1) + 1 = 24 + 23 + 22 + 2 + 1
R6 = 2 · (24 + 23 + 22 + 2 + 1) + 1 = 25 + 24 + 23 + 22 + 2 + 1

So it looks like:
Rn = 2n−1 + 2n−2 + · · · + 22 + 2 + 1
Now, using the theorem on geometric series

n
X a(1 − rn )
ark = Sn = a + ar + ar2 + ar3 + · · · + arn−1 =
1−r
k=0

we obtain the following formula where a = 1, r = 2:

1 − 2n
2n−1 + 2n−2 + · · · + 22 + 2 + 1 = 1 · = 2n − 1
1−2
We should verify the correctness of the formula to be sure. We will prove this by mathematical
induction.
Hypothesis: Rn = 2Rn−1 + 1 = 2n − 1

8
 Proof (by induction)
R1 = 21 − 1 = 1
Now, let us assume that the theorem is true for n − 1, and we must prove from this that it
is also true for n. We start from the recurrence formula:

Rn = 2Rn−1 + 1
We substitute 2n−1 − 1 in place of Rn−1 , according to the inductive assumption.

Rn = 2(2n−1 − 1) + 1
Rn = 2 · 2n−1 − 2 + 1
Rn = 2n − 1

9 Divide and Conquer Paradigm and the Substitution Method

Divide and conquer is one of the main methods of algorithm design in computer science, leading
to very ecient solutions. The name comes from the Latin maxim divide and rule (Latin:
divide et impera). In this strategy, the problem is recursively divided into two or more smaller
subproblems of the same (or similar) type, until the fragments become simple enough for direct
solution. In turn, the solutions obtained for the subproblems are merged, obtaining a solution
to the entire task. We have already initially discussed two examples of this type of algorithm:
binary search and merge sort.
The general recursive scheme of divide and conquer algorithms has the following form:

Pn = aPn/b + f (n)
where a, b ∈ N are parameters concerning the number of divisions and the specics of the
algorithm, and f (n) is a function with parameter n or a constant term (e.g., a constant) also
depending on the specics of the algorithm. Most often in practice  when the problem is
successively divided into two subproblems  the form is as follows:

Pn = aPn/2 + f (n)
Example 9.1. The recurrence for the number of comparisons in the binary search algorithm
has the following parameters: a = 1, b = 2, and f (n) = 1. That is:

Pn = Pn/2 + 1, P1 = 0
Example 9.2. The recurrence for the number of comparisons in the merge sort algorithm has
the following parameters: a = 2, b = 2, and f (n) = n − 1, because it should be noted that we
obtain the special case Pn = 2Pn−1 + 2n − 1, if we assume that n = 2k for some k ∈ N in the
following formula:
Pn = 2Pn/2 + n − 1
Example 9.3 (Solution of the Recurrence for the Number of Comparisons in Binary Search by
the Substitution Method).

Pn = Pn/2 + 1 Pn/2 = Pn/4 + 1

= (Pn/22 + 1) + 1 Pn/22 = Pn/23 + 1
= ((Pn/23 + 1) + 1) + 1 Pn/23 = Pn/24 + 1
= (((Pn/24 + 1) + 1) + 1) + 1
.
.
.

= Pn/2k + k
= P1 + k

9
 n
For what value of k does Pn/2k = P1 hold? If
2k
=1 then n = 2k , i.e., k = log n.
Therefore Pn = P1 + k = log n.

Exercise 9.1. Solve the merge sort recurrence by the substitution method.

10 Linear Homogeneous Recurrence Equations with Constant

Coecients
Denition 10.1. A linear homogeneous recurrence equation of order p with constant coecients
is an equation of the form:

xn = c1 xn−1 + c2 xn−2 + · · · + cp xn−p

for certain constants c1 , c2 , . . . , cp ∈ R \ {0}. The initial (boundary) condition of equation (1) is
the equalities determining the initial p terms of the sequence x1 , x2 , . . . , xp−1 .
A solution to the recurrence equation is any numerical sequence (rn )n≥0 that satises the
equation.

The following discussion and the theorems and methodology contained therein concern equa-
tions of any order, but for simplicity we will focus on linear homogeneous recurrence equations
with constant coecients of the second order.

Denition 10.2. A second-order linear homogeneous recurrence equation with constant coe-
cients is a recurrence equation of the form:

an = Aan−1 + Ban−2

where A, B ∈ R, and B ̸= 0.

Let us begin this section with a preliminary discussion, preliminarily motivating the main
theorem. Consider the linear homogeneous second-order recurrence equation with constant
coecients:
an = Aan−1 + Ban−2
Relation (2) is satised when all ai = 0 , but it also has nonzero solutions. Suppose that for
some number t with t ̸= 0 the sequence

1, t, t2 , t3 , . . . , tn , . . .

satises relation (2). This means that each term of the sequence equals A times the previous
term plus B times the term two terms before. Thus for all integers n ≥ 2,

tn = Atn−1 + Btn−2

Dividing by tn−2 we obtain:

t2 = At + B
or equivalently,
t2 − At − B = 0
This is a quadratic equation, and the values of t are the roots that satisfy it. We also call it
the characteristic equation of recurrence relation (2).
A few more formal steps are needed to justify the following theorem, but their details are
not crucial for us. For those interested, I recommend reading the following material: Susanna
Epp (Section 5.8), Ross & Wright (Section 4.4).

10
10.1 Case 1: Two Roots
Theorem 10.1. Suppose that the sequence a0 , a1 , a2 , . . . satises the recurrence relation
an = Aan−1 + Ban−2

If the characteristic equation x2 − Ax − B = 0 has two distinct roots r1 , r2 ∈ R, then the

sequence a0 , a1 , a2 , . . . has an explicit formula of the form:
an = c1 r1n + c2 r2n

where c1 , c2 are arbitrary constants whose values can be determined from the initial conditions
a0 and a1 .

10.2 Case 2: One Root

Theorem 10.2. Suppose that the sequence a0 , a1 , a2 , . . . satises the recurrence relation
an = Aan−1 + Ban−2

If the characteristic equation x2 − Ax − B = 0 has one root r ∈ R, then the sequence

a0 , a1 , a2 , . . . has an explicit formula of the form:

an = c1 rn + c2 nrn

where c1 , c2 are arbitrary constants whose values can be determined from the initial conditions
a0 and a1 .

Example 10.1 (Two Distinct Roots). Consider the recurrence relation sn = sn−1 + 2sn−2 , with
initial conditions s0 = s1 = 3. So A = 1, B = 2.
The characteristic equation x2 −x−2 = 0 has solutions r1 = 2, r2 = −1, because x2 −x−2 =
(x−2)(x+1). Therefore the case of the theorem concerning two solutions applies. So the general
solution has the form:
sn = c1 · 2n + c2 (−1)n
For certain constants c1 , c2 ∈ R and for n ∈ N. Substituting n=0 and n=1 we obtain:

s0 = c1 · 20 + c2 (−1)0 = c1 + c2 = 3
s1 = c1 · 21 + c2 (−1)1 = 2c1 − c2 = 3

c2 = 3 − c1 , from the rst equation. Substituting c2 into the second equation

So we obtain
2c1 − (3 − c1 ) = 3, so 3c1 = 6, i.e., c1 = 2. Therefore c2 = 1. So nally we have:

sn = 2 · 2n + 1 · (−1)n = 2n+1 + (−1)n

for n ∈ N.

Example 10.2 (One Root). Consider the sequence (sn )n∈N dened by the formulas for n ≥ 2:

s0 = 1, s1 = −3, sn = 6sn−1 − 9sn−2

The characteristic equation is x2 − 6x + 9 = 0, which has one solution, namely r = 3, because

x2 − 6x + 9 = (x − 3)2 , so the general solution of the recurrence has the form:

sn = c1 · 3n + c2 n · 3n

For certain constants c1 , c2 ∈ R and n ∈ N.

11
 Substituting n=0 and n=1 we obtain:

s0 = c1 · 30 + c2 · 0 · 30 = c1 = 1
s1 = c1 · 31 + c2 · 1 · 31 = 3c1 + 3c2 = −3

So 3c2 = −6, therefore c2 = −2. Hence:

sn = 3n − 2n · 3n for n ∈ N.

Example 10.3 (Fibonacci Sequence). Consider the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, . . .

We know that it satises the following recurrence relation:

F0 = 1, F1 = 1, Fn = Fn−1 + Fn−2

The characteristic equation of this recurrence has the form x2 − x − 1 = 0. We solve using
the formula: √
−b ± b2 − 4ac
x=
2a
For ax2 + bx + c = 0. So in our case:
p √
−(−1) ± (−1)2 − 4 · 1 · (−1) 1± 5
x= =
2·1 2
So, we have two roots:
√ √
1+ 5 1− 5
r1 = , r2 =
2 2
So the general solution has the following form:

√ !n √ !n
1+ 5 1− 5
Fn = c1 r1n + c2 r2n = c1 + c2
2 2

for n ∈ N.
(Note that r1 is the so-called golden ratio, resulting from the golden section.)
To determine c1 and c2 , it will be more convenient to keep the notations r1 and r2 . Substi-
tuting n=0 and n = 1, and the fact that s0 = s1 = 1, we obtain:

c1 + c2 = 1 and c1 r1 + c2 r2 = 1

If we substitute c2 = 1 − c1 into the second equation, we obtain c1 r1 + (1 − c1 )r2 = 1, so

c1 r1 + r2 − c1 r2 = 1, i.e., c1 (r1 − r2 ) = 1 − r2 , and:
1 − r2
c1 =
r1 − r2
√ r1
Since r1 + r2 = 1 and r1 − r2 = 5, it follows that c1 = √
5
. Then c2 = 1 − c1 = 1 − √r15 , i.e.,
√
5−r −r
c2 = √ 1
5
= √ 2 . Finally
5

r1 r2 1
Fn = c1 r1n + c2 r2n = √ r1n − √ r2n = √ (r1n+1 − r2n+1 )
5 5 5
Therefore
√ !n+1 √ !n+1
 
1  1+ 5 1− 5
Fn = √ − 
5 2 2

12