Design and Analysis of Algorithms

Solutions of Recurrence Relations 703

D.2 PRELIMINARIES

D.2.1 Sequences and Generating Functions

We have seen in Appendix A that sequences are functions whose domain is a set of non-negative integers and

range is a set of real numbers.

Let a sequence A =

{}

0

r

r

a

∞

=

. This sequence can be represented by an associated formal power series

A(X) = a

0

+ a

1

X + a

2

X

2

+ . . . + a

n

X

n

+ . . . = a

n

X

n

0

r

∞

=

∑

a

r

X

r

.

This is called ordinary generating function or simply generating function of the sequence. Note that the

variable X has no signifi cance other than a place holder for the corresponding coeffi cient a

n

.

It is possible that all the coefficients are zero beyond certain value of n = k. In that case A(X) is a

polynomial of degree k.

The following operations are ...