Methods in Algorithmic Analysis

Chapter 12

Review of Analytic Techniques

In this chapter, we recall the deﬁnitions and properties of the mathematical infrastructure

needed to accommodate generating functions (GFs). While we include sufﬁcient material for

our uses here, the reader who would like to get more deeply into these topics needs additional

sources; happily, excellent texts exist. We recommend P. Henrici [62] for a detailed modern

coverage; all our current needs are satisﬁed by the ﬁrst chapter there.

12.1 Complex Numbers

We start with a reprise of complex numbers.

Deﬁnition 12.1 A complex number

is an ordered pair of real numbers. A standard notation

is z = (x,y), where the real number x is called the real part of the complex number z, and the

real number y is called the imaginary part of z. The common notation for these components

ℜz = x, ℑz = y

Two complex numbers are equal when their real and imaginary components are equal sepa-

rately. The set of all ordered pairs of real numbers is called the set or the ﬁeld of complex

numbers, denoted by C, if the following arithmetic operations hold. Let z

= (x

), z

) be two complex numbers; they can be manipulated as follows:

1. S um. Addition is deﬁned as

+ z

= (x

+ x

, y

+ y

2. Difference. S ubtraction is similarly deﬁned via

−z

= (x

−x

, y

−y

Complex numbers were so named by Carl Friedrich Gauss (1777–1855), but were known to mathematicians

for several centuries earlier. The symbol i for the imaginary unit was introduced by Leonhard Euler in 1777.

661

662

Chapter 12. Review of Analytic Techniques

3. Multiplication. The product is given by

= (x

−y

+ x

4. Division. This is easily derived from the multiplication:



+ y

−x

+ y



. ⊳

While the real numbers constitute the real line, complex numbers span the complex plane.

We denote by 1 = (1,0) and i = (0,1) the unit vectors along the coordinate axes Ox and Oy.

In electrical engineering, it is common to denote these unit vectors as i = (1,0) and j = (0,1).

The abscissa is also called in this context the real axis; naturally, the ordinate then becomes

the imaginary axis.

The deﬁnition of the multiplication operation provides (0,1) ×(0,1) = (−1,0), or i

= −1,

so we see that the imaginary unit is, up to a sign,

√

−1. In other words:

√

−1 = ±i.

Let the projections of a complex number z on these axes be x = ℜz and y = ℑz. Then the

representation of z in terms of these components is

z = x1 + yi or simply z = x + iy. (12.1)

This is called the Cartesian form of a complex number. In MAPLE, the imaginary unit is

denoted by I, hence this number would be written as z = x + Iy. There is no difference

between x + iy and x + yi; for brevity w e write x instead of x + i0, and iy instead of 0 + iy.

The former complex number is said to be

pure real

and the latter—a

pure imaginary

..... ..... ..... ..... .....

.... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... .... ....

= x

+ iy

= x

+ iy

+ z

= (x

+ x

) + i(y

+ y

)

z = x + iy

z = x −iy

]

Figure 662: (a) Addition of complex numbers (b) Polar representation

Deﬁnition 12.2 The complex number x −iy is called the conjugate of the complex number

z = x + iy and is denoted by z = x −iy. ⊳

Multiplications or divisions are easier—and more natural—in the polar representation of

complex numbers, than in the Cartesian form (12.1). We place the “pole” at the origin 0 of

Get Methods in Algorithmic Analysis now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Methods in Algorithmic Analysis by Vladimir A. Dobrushkin

Don’t leave empty-handed

It’s yours, free.

Check it out now on O’Reilly