1- RECURRENCE RELATIONS
Previously, we discussed recursively de?ned functions such as
(a) Factorial function, (b) Fibonacci sequence, (c) Ackermann function.
Here we discuss certain kinds of recursively de?ned sequences {an } and their solution. We note that a sequence
is simply a function whose domain is
N = {1, 2, 3,.. .} or N0 = N ? {0}= {0, 1, 2, 3,.. .]
We begin with some examples.
EXAMPLE 7 Consider the following sequence which begins with the number 3 and for which each of the following terms is found by multiplying the previous term by 2:
3, 6, 12, 24, 48, ...
It can be de?ned recursively by:
a0 = 3, ak = 2ak?1 for k ? 1 or a0 = 3, ak+1 = 2ak for k ? 0
The second de?nition may be obtained from the ?rst by setting k = k + 1. Clearly, the formula an = 3(2n ) gives us the nth term of the sequence without calculating any previous term.
The following remarks about the above example are in order.
(1) The equation ak = 2ak?1 or, equivalently, ak+1 = 2ak , where one term of the sequence is de?ned in terms of previous terms of the sequence, is called a recurrence relation.
(2) The equation a0 = 3, which gives a speci?c value to one of the terms, is called an initial condition.
(3) The function an = 3(2n ), which gives a formula for an as a function of n, not of previous terms, is called
a solution of the recurrence relation.
(4) There may be many sequences which satisfy a given recurrence relation. For example, each of the following is a solution of the recurrence relation ak = 2ak?1 .
1, 2, 4, 8, 16,... and 7, 14, 28, 56, 112,...
All such solutions form the so-called general solution of the recurrence relation.
(5) On the other hand, there may be only a unique solution to a recurrence relation which also satis?es given initial conditions. For example, the initial condition a0 = 3 uniquely yields the solution 3, 6, 12, 24,... of the recurrence relation ak = 2ak?1 .
This chapter shows how to solve certain recurrence relations. First we give two important sequences the reader may have previously studied.
EXAMPLE 8
(a) Arithmetic Progression
An arithmetic progression is a sequence of the form
a, a + d, a + 2d, a + 3d ,...
That is, the sequence begins with the number a and each successive term is obtained from the previous term by adding d (the common difference between any two terms). For example:
(i) a = 5, d = 3: 5, 8, 9, 11,...
(ii) a = 2, d = 5: 2, 7, 12, 17,...
(iii) a = 1, d = 0: 1, 1, 1, 1, 1,...
We note that the general arithmetic progression may be de?ned recursively by:
a1 = a and ak+1 = ak + d for k ? 1 where the solution is an = a + (n ? 1)d .
(b) Geometric Progression
A geometric progression is a sequence of the form
a, ar, ar 2 , ar 3 ,...
That is, the sequence begins with the number a and each successive term is obtained from the previous term by multiplying by r (the common ratio between any two terms) for example:
(i) a = 1, r = 3: 1, 3, 9, 27, 81,...
(ii) a = 5, r = 2: 5, 10, 20, 40,...
(iii) a = 1, r = 1 : 1, 1 , 1 , 1 ,...
2 2 4 8
We note that the general geometric progression may be de?ned recursively by:
a1 = a and ak+1 = rak for k ? 1 where the solution is an+1 = ar n .
2- LINEAR RECURRENCE RELATIONS WITH CONSTANT COEFFICIENTS
A recurrence relation of order k is a function of the form
an = ?(an?1, an?2 ,..., an?k , n)
that is, where the nth term an of a sequence is a function of the preceding k terms an?1 , an?2 ,..., an?k (and possibly n). In particular, a linear kth-order recurrence relation with constant coef?cients is a recurrence relation
of the form
an = C1 an?1 + C2 an?2 + ••• + Ck an?k + f (n)
where C1 , C2 ,..., Ck are constants with Ck = 0, and f (n) is a function of n. The meanings of the names linear
and constant coef?cients follow:
Linear: There are no powers or products of the aj ’s.
Constant coef?cients: The C1 C2 ,... ,Ck are constants (do not depend on n).
If f (n) = 0, then the relation is also said to be homogeneous.
Clearly, we can uniquely solve for an if we know the values of an?1 , an?2 ,..., an?k . Accordingly, by mathematical induction, there is a unique sequence satisfying the recurrence relation if we are given initial values
for the ?rst k elements of the sequence.