112 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6
The following remarks about the above example are in order.
(1) The equationak= 2 ak− 1 or, equivalently,ak+ 1 = 2 ak, where one term of the sequence is defined in
terms of previous terms of the sequence, is called arecurrence relation.
(2) The equationa 0 =3, which gives a specific value to one of the terms, is called aninitial condition.
(3) The functionan= 3 ( 2 n), which gives a formula foranas a function ofn, not of previous terms, is called
asolutionof 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 relationak= 2 ak− 1.
1 , 2 , 4 , 8 , 16 ,... and 7, 14 , 28 , 56 , 112 ,...
All such solutions form the so-calledgeneral solutionof the recurrence relation.
(5) On the other hand, there may be only a unique solution to a recurrence relation which also satisfies given
initial conditions. For example, the initial conditiona 0 =3 uniquely yields the solution 3, 6 , 12 , 24 ,...
of the recurrence relationak= 2 ak− 1.
This chapter shows how to solve certain recurrence relations. First we give two important sequences the reader
may have previously studied.
EXAMPLE 6.8
(a) Arithmetic Progression
An arithmetic progression is a sequence of the form
a, a+d,a+ 2 d,a+ 3 d,...
That is, the sequence begins with the numberaand each successive term is obtained from the previous
term by addingd(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 defined recursively by:
a 1 =a and ak+ 1 =ak+d fork≥ 1
where the solution isan=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 numberaand each successive term is obtained from the previous term
by multiplying byr(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=^12 :1,^12 ,^14 ,^18 ,...
We note that the general geometric progression may be defined recursively by:
a 1 =a and ak+ 1 =rak fork≥ 1
where the solution isan+ 1 =arn.