Methods in Algorithmic Analysis

Chapter 5

Recurrences or Difference Equations

Sequences, also known as functions of a discrete variable, appear in many applications of

computer science, in numerical analysis, and, naturally, in discrete mathematics. Many of

these applications are rooted in practical, engineering problems, where systems have a fi nite

or denumerable state space. Other such scenarios arise when systems change their state at

discrete instants of time only. A recurrence is an equation that describes the evolution or

behavior of such a function.

In this chapter, we present many such equations, and solve only a few special types. More

solutions will be introduced and derived in subsequent chapters. A major application that

relies on recurrences is the derivation of numerical approximation schemes for differential

equations, obtained by a discretization of the continuous problem space; this scenario is

not our objective here. However, a special section (§5.6) is dedicated to some numerical

approximations.

In general, a recurrence is used to find out the properties of a sequence, numeric or symbolic.

In our applications, a sequence almost always is a function defined on a set of integers,

typically, N = {0,1,2,...} with values in the set of real (or complex) numbers. Traditionally,

terms of sequences are denoted by subscripted symbols such as a

n

rather than a(n). There w ill

be exceptions, for example, when the subscripts become complex; thus we prefer A(⌈

n

2

2

⌉) to

A

⌈

n

2

2

⌉

. A sequence is usually denoted by {a

n

}

∞

n=0

or {a

n

}

n>0

or simply {a

n

}, when the range

is obvious. If a sequence of interest is finite, it is assumed to be embedded into an infinite

one typically padded with zeroes.

Infinite sequences also exist outside analysis of algorithms. For example, they arise in com-

munication whenever we consider a signal that is sampled at discrete times. A signal might

be electrical, mechanical, or optical. Control systems for the space shuttle, modern aircrafts,

or any complex system now use discrete or “digital” signals. The clear sounds from a com-

pact disc player are produced from music sampled at the rate of 44,100 times per second. At

each measurement, the amplitude of the music signal is recorded as a number, say, x

k

. This

sequence {x

k

} contains enough information to reproduce the music with high fidelity.

199