DM Recurrences PDF

CHAPTER 5
Recurrence Relations
5.1. Recurrence Relations
Here we look at recursive definitions under a different point of view.

Rather than definitions they will be considered as equations that we
must solve. The point is that a recursive definition is actually a def-
inition when there is one and only one object satisfying it, i.e., when
the equations involved in that definition have a unique solution. Also,
the solution to those equations may provide a closed-form (explicit)
formula for the object defined.
The recursive step in a recursive definition is also called a recurrence
relation. We will focus on kth-order linear recurrence relations, which
are of the form
C0 xn + C1 xn1 + C2 xn2 + + Ck xnk = bn ,
where C0 6= 0. If bn = 0 the recurrence relation is called homogeneous.
Otherwise it is called non-homogeneous.
The basis of the recursive definition is also called initial conditions
of the recurrence. So, for instance, in the recursive definition of the
Fibonacci sequence, the recurrence is
Fn = Fn1 + Fn2
or
Fn Fn1 Fn2 = 0 ,
and the initial conditions are
F0 = 0, F1 = 1 .
One way to solve some recurrence relations is by iteration, i.e., by

using the recurrence repeatedly until obtaining a explicit close-form
formula. For instance consider the following recurrence relation:
xn = r xn1 (n > 0) ; x0 = A .
76
5.1. RECURRENCE RELATIONS 77
By using the recurrence repeatedly we get:

xn = r xn1 = r2 xn2 = r3 xn3 = = rn x0 = A rn ,
hence the solution is xn = A rn .
In the following we assume that the coefficients C0 , C1 , . . . , Ck are
constant.
5.1.1. First Order Recurrence Relations. The homogeneous

case can be written in the following way:
xn = r xn1 (n > 0) ; x0 = A .
Its general solution is
xn = A r n ,
which is a geometric sequence with ratio r.
The non-homogeneous case can be written in the following way:
xn = r xn1 + cn (n > 0) ; x0 = A .
Using the summation notation, its solution can be expressed like this:
X
n
n
xn = A r + ck rnk .
k=1
We examine two particular cases. The first one is

xn = r xn1 + c (n > 0); x0 = A .
where c is a constant. The solution is
X n
rn 1
n
xn = A r + c rnk = A rn + c if r 6= 1 ,
k=1
r1
and
xn = A + c n if r = 1 .
Example: Assume that a country with currently 100 million people

has a population growth rate (birth rate minus death rate) of 1% per
year, and it also receives 100 thousand immigrants per year (which
are quickly assimilated and reproduce at the same rate as the native
population). Find its population in 10 years from now. (Assume that
all the immigrants arrive in a single batch at the end of the year.)
Answer : If we call xn = population in year n from now, we have:

xn = 1.01 xn1 + 100, 000 (n > 0); x0 = 100, 000, 000 .
This is the equation above with r = 1.01, c = 100, 000 and A =
100, 000, 00, hence:
1.01n 1
xn = 100, 000, 000 1.01n + 100, 000
1.01 1
= 100, 000, 000 1.01n + 1000 (1.01n 1) .
So:
x10 = 110, 462, 317 .
The second particular case is for r = 1 and cn = c + d n, where c

and d are constant (so cn is an arithmetic sequence):
xn = xn1 + c + d n (n > 0) ; x0 = A .
The solution is now
Xn
d n (n + 1)
xn = A + (c + d k) = A + c n + .
k=1
2
5.1.2. Second Order Recurrence Relations. Now we look at

the recurrence relation
C0 xn + C1 xn1 + C2 xn2 = 0 .
First we will look for solutions of the form xn = c rn . By plugging in
the equation we get:
C0 c rn + C1 c rn1 + C2 c rn2 = 0 ,
hence r must be a solution of the following equation, called the char-
acteristic equation of the recurrence:
C0 r2 + C1 r + C2 = 0 .
Let r1 , r2 be the two (in general complex) roots of the above equation.
They are called characteristic roots. We distinguish three cases:
1. Distinct Real Roots. In this case the general solution of the

recurrence relation is
xn = c1 r1n + c2 r2n ,
where c1 , c2 are arbitrary constants.
2. Double Real Root. If r1 = r2 = r, the general solution of the

recurrence relation is
xn = c1 rn + c2 n rn ,
where c1 , c2 are arbitrary constants.
3. Complex Roots. In this case the solution could be expressed
in the same way as in the case of distinct real roots, but in
order to avoid the use of complex numbers we write r1 = r ei ,
r2 = r ei , k1 = c1 + c2 , k2 = (c1 c2 ) i, which yields:1
xn = k1 rn cos n + k2 rn sin n .
Example: Find a closed-form formula for the Fibonacci sequence

defined by:
Fn+1 = Fn + Fn1 (n > 0) ; F0 = 0, F1 = 1 .
Answer : The recurrence relation can be written
Fn Fn1 Fn2 = 0 .
The characteristic equation is
r2 r 1 = 0 .
Its roots are:2

1+ 5 1 1 5
r1 = = ; r2 = = .
2 2
They are distinct real roots, so the general solution for the recurrence
is:
Fn = c1 n + c2 (1 )n .
Using the initial conditions we get the value of the constants:
(
(n = 0) c1 + c2 = 0 c1 = 1/5

(n = 1) c1 + c2 (1 ) = 1 c2 = 1/ 5
Hence:
1 n
Fn = ()n .
5
1Reminder: ei = cos + i sin .

2 = 1+ 5
is the Golden Ratio.
2

DM Recurrences PDF

Uploaded by

Copyright:

Available Formats

DM Recurrences PDF

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DM Recurrences PDF

Uploaded by

Copyright:

Available Formats

CHAPTER 5

5.1. Recurrence Relations

Here we look at recursive definitions under a different point of view.

One way to solve some recurrence relations is by iteration, i.e., by

By using the recurrence repeatedly we get:

5.1.1. First Order Recurrence Relations. The homogeneous

We examine two particular cases. The first one is

Example: Assume that a country with currently 100 million people

Answer : If we call xn = population in year n from now, we have:

The second particular case is for r = 1 and cn = c + d n, where c

5.1.2. Second Order Recurrence Relations. Now we look at

1. Distinct Real Roots. In this case the general solution of the

2. Double Real Root. If r1 = r2 = r, the general solution of the

Example: Find a closed-form formula for the Fibonacci sequence

1Reminder: ei = cos + i sin .

You might also like