Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

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.