Recurrence

Relations

1
 Recurrence Relations
A recurrence relation for the sequence {an} is an
equation that expresses an is terms of one or
more of the previous terms of the sequence,
namely, a0, a1, …, an-1, for all integers n with
n  n0, where n0 is a nonnegative integer.

A sequence is called a solution of a recurrence

relation if it terms satisfy the recurrence
relation.

2
 Problem
A pair of newly born rabbits of opposite sexes is placed in an
enclosure at the beginning of a year. Baby rabbits need one
moth to grow mature; they become an adult pair on the first
day of the second month. Beginning with the second month
the female is pregnant, and gives exactly one birth of one
pair of rabbits of opposite sexes on the first day of the
third month, and gives exactly one such birth on the first
day of each next month. Each new pair also gives such birth
to a pair of rabbits on the first day of each month starting
from the third month (from its birth). Find the number of
pairs of rabbits in the enclosure after one year?

SOLVE THE PROBLEM

3
Some useful formulae

4
 Recurrence Relations
Example:
Consider the recurrence relation
an = 2an-1 – an-2 for n = 2, 3, 4, …

Is the sequence {an} with an=3n a solution of this

recurrence relation?
For n  2 we see that
2an-1 – an-2 = 2(3(n – 1)) – 3(n – 2) = 3n = an.
Therefore, {an} with an=3n is a solution of the
recurrence relation.

5
 Recurrence Relations

Is the sequence {an} with an=5 a solution of the

same recurrence relation?
For n  2 we see that
2an-1 – an-2 = 25 - 5 = 5 = an.
Therefore, {an} with an=5 is also a solution of the
recurrence relation.

6
 Modeling with Recurrence Relations
Example:
Someone deposits $10,000 in a savings account at
a bank yielding 5% per year with interest
compounded annually. How much money will be in
the account after 30 years?
Solution:
Let Pn denote the amount in the account after n
years.
How can we determine Pn on the basis of Pn-1?

7
 Modeling with Recurrence Relations
We can derive the following recurrence relation:
Pn = Pn-1 + 0.05Pn-1 = 1.05Pn-1.
The initial condition is P0 = 10,000.
Then we have:
P1 = 1.05P0
P2 = 1.05P1 = (1.05)2P0
P3 = 1.05P2 = (1.05)3P0
…
Pn = 1.05Pn-1 = (1.05)nP0

We now have a formula to calculate Pn for any

natural number n and can avoid the iteration.
8
 Modeling with Recurrence Relations

Let us use this formula to find P30 under the

initial condition P0 = 10,000:

P30 = (1.05)3010,000 = 43,219.42

After 30 years, the account contains $43,219.42.

9
 Solving Recurrence Relations

In general, we would prefer to have an explicit

formula to compute the value of an rather than
conducting n iterations.
For one class of recurrence relations, we can
obtain such formulas in a systematic way.
Those are the recurrence relations that express
the terms of a sequence as linear combinations of
previous terms.

10
 Solving Recurrence Relations
Definition: A linear homogeneous recurrence
relation of degree k with constant coefficients is
a recurrence relation of the form:
an = c1an-1 + c2an-2 + … + ckan-k,
Where c1, c2, …, ck are real numbers, and ck  0.

A sequence satisfying such a recurrence relation

is uniquely determined by the recurrence relation
and the k initial conditions
a0 = C0, a1 = C1, a2 = C2, …, ak-1 = Ck-1.

11
 Solving Recurrence Relations
Examples:
The recurrence relation Pn = (1.05)Pn-1
is a linear homogeneous recurrence relation of
degree one.
The recurrence relation fn = fn-1 + fn-2
is a linear homogeneous recurrence relation of
degree two.
The recurrence relation an = an-5
is a linear homogeneous recurrence relation of
degree five.

12
 Solving Recurrence Relations
Basically, when solving such recurrence relations,
we try to find solutions of the form an = rn,
where r is a constant.
an = rn is a solution of the recurrence relation
an = c1an-1 + c2an-2 + … + ckan-k if and only if
rn = c1rn-1 + c2rn-2 + … + ckrn-k.
Divide this equation by rn-k and subtract the
right-hand side from the left:
rk - c1rk-1 - c2rk-2 - … - ck-1r - ck = 0
This is called the characteristic equation of the
recurrence relation.
13
 Solving Recurrence Relations
The solutions of this equation are called the
characteristic roots of the recurrence relation.
Let us consider linear homogeneous recurrence
relations of degree two.
Theorem: Let c1 and c2 be real numbers. Suppose
that r2 – c1r – c2 = 0 has two distinct roots r1 and r2.
Then the sequence {an} is a solution of the
recurrence relation an = c1an-1 + c2an-2 if and only if an
= 1r1n + 2r2n for n = 0, 1, 2, …, where 1 and 2 are
constants.

14
Solving Recurrence Relations
A linear homogeneous recurrence relation of
degree k with constant coefficient is a
recurrence relation of the form
an = c1an−1 + … + ckan−k,
where the ci are all real, and ck ≠ 0.
The solution is uniquely determined if k initial
conditions a0…ak−1 are provided

15
 Solving Recurrence Relations

Example: What is the solution of the recurrence

relation an = an-1 + 2an-2 with a0 = 2 and a1 = 7 ?

Solution: The characteristic equation of the

recurrence relation is r2 – r – 2 = 0.
Its roots are r = 2 and r = -1.
Hence, the sequence {an} is a solution to the
recurrence relation if and only if:
an = 12n + 2(-1)n for some constants 1 and 2.

16
 Solving Recurrence Relations
Given the equation an = 12n + 2(-1)n and the initial
conditions a0 = 2 and a1 = 7, it follows that
a0 = 2 = 1 + 2
a1 = 7 = 12 + 2 (-1)

Solving these two equations gives us

1 = 3 and 2 = -1.

Therefore, the solution to the recurrence relation

and initial conditions is the sequence {an} with
an = 32n – (-1)n.
17
 Solving Recurrence Relations
an = rn is a solution of the linear homogeneous
recurrence relation
an = c1an-1 + c2an-2 + … + ckan-k
if and only if
rn = c1rn-1 + c2rn-2 + … + ckrn-k.
Divide this equation by rn-k and subtract the
right-hand side from the left:
rk - c1rk-1 - c2rk-2 - … - ck-1r - ck = 0
This is called the characteristic equation of the
recurrence relation.

18
 Solving Recurrence Relations
The solutions of this equation are called the
characteristic roots of the recurrence relation.
Let us consider linear homogeneous recurrence
relations of degree two.
Theorem: Let c1 and c2 be real numbers. Suppose
that r2 – c1r – c2 = 0 has two distinct roots r1 and r2.
Then the sequence {an} is a solution of the
recurrence relation an = c1an-1 + c2an-2 if and only if an
= 1r1n + 2r2n for n = 0, 1, 2, …, where 1 and 2 are
constants.

19
 Solving Recurrence Relations

Example: Give an explicit formula for the Fibonacci

numbers.
Solution: The Fibonacci numbers satisfy the
recurrence relation fn = fn-1 + fn-2 with initial
conditions f0 = 0 and f1 = 1.
The characteristic equation is r2 – r – 1 = 0.
Its roots are
1+ 5 1− 5
r1 = , r2 =
2 2

20
 Solving Recurrence Relations
Therefore, the Fibonacci numbers are given by
n n
1+ 5  1− 5 
f n =  1   +2
  2 

 2   
for some constants 1 and 2.
We can determine values for these constants so
that the sequence meets the conditions f0 = 0
and f1 = 1:
f0 = 1 +  2 = 0
1+ 5  1− 5 
f1 =  1   +2
  2 
 =1
 2   
21
 Generating Functions

Given a sequence <g0,g1,g2,g3,………>

the ordinary generating function is:

We use a double-sided arrow to indicate

the correspondence.
Examples
 Solving Recurrence Relations
The unique solution to this system of two
equations and two variables is
1 1
1 = , 2 = −
5 5
So finally we obtained an explicit formula for the
Fibonacci numbers:
n n
1 1+ 5  1 1− 5 
fn =   −  
5  2  5  2 

24
 Solving Recurrence Relations

If the “largest” index term in the recurrence is an,

and the “smallest” index term is an−k, the
characteristic equation will be a polynomial of
degree k. There will be a non-zero term involving x
k−t whenever an−t is involved in the recurrence.

25
 Solving Recurrence Relations

But what happens if the characteristic equation

has only one root?
How can we then match our equation with the initial
conditions a0 and a1 ?
Theorem: Let c1 and c2 be real numbers with c2  0.
Suppose that r2 – c1r – c2 = 0 has only one root r0.
A sequence {an} is a solution of the recurrence
relation an = c1an-1 + c2an-2 if and only if
an = 1r0n + 2nr0n, for n = 0, 1, 2, …, where 1 and 2
are constants.

26
 Solving Recurrence Relations
Example: What is the solution of the recurrence
relation an = 6an-1 – 9an-2 with a0 = 1 and a1 = 6?
Solution: The only root of r2 – 6r + 9 = 0 is r0 = 3.
Hence, the solution to the recurrence relation is
an = 13n + 2n3n for some constants 1 and 2.
To match the initial condition, we need
a0 = 1 = 1
a1 = 6 = 13 + 23
Solving these equations yields 1 = 1 and 2 = 1.
Consequently, the overall solution is given by
an = 3n + n3n.
27
28
29
30
31
32
33