Chapter 11
Asymptotics and Ge n e rating
Functions
In Chapters 6 – 8, we have seen several applications of generating functions (GFs) where
we disregard the issue of convergence of the defining series because it plays no role. The
series were viewed as formal power series. The question whether the ordinary or exponential
generating function has a meaning as an expansion of an analytical entity needs not even be
considered—the answer was not essential for generating functions used so successfully.
In this chapter, we change a dominant theme in our music since it is precisely the question of
convergence, including analyticity, and the location and type of singularities, that play a lead-
ing role in deducing asymptotic information from generating functions. This musical change
will provide some sweet harmonies. Also we present some statements without proofs (formu-
lated as theorems) from advanced calculus and the theory of power series. More information
can be found in [14, 103, 105 ].
Note: Much of the material in this chapter relies on the concepts developed in Chapter 12,
especially §12.3. We recommend a review of functions of a complex variable.
11.1 Elementary Bounds from Generating Functions
Let {f
n
} be a sequence of numbers and f (z) be its ordinary generating function,
f (z) =
∑
n>0
f
n
z
n
. (11.1)
What information do we get from the simple fact that the series converges? We can get
the limit of f
n
from f (z) by using the Abel theorem L.86, page 740. Let us examine the
evidence: we know that the series
∑
k>0
z
k
converges to (1 −z)
−1
only for |z| < 1. And the
similar geometric series,
∑
k>0
(cz)
k
equals (1 −cz)
−1
only in the circle |z| < 1/c. In the first
629
630
Chapter 11. Asymptotics and Generating Functions
case the coefficients of z
k
in the series were all 1, and in the second case the latter series has
coefficients c
k
.
Surely, we can conclude that in order for the series in Eq. (11.1) to converge in some circle
|z| < R, it is sufficient that f
n
< R
n
, at least beyond some finite index n
0
since the values of
any finite number of elements do not impact the series convergence property. They definitely
change the value of the limit, but not the fact that it converges. This R is called the radius of
convergence of the series.
Theorem 11.1 The radius of convergence of a power series F(z) =
∑
k>0
c
k
(z −z
0
)
k
is the
distance of the singular point of the function F(z) closest to z
0
.
A more precise expression of the radius of convergence is Cauchy’s nth-root convergence
test. It says that for the series in Eq. (11.1) to have the radius of convergence R, the following
one-sided limits must exist:
R = lim
|f
n
|
−1/n
or R
−1
= lim|f
n
|
1/n
. (11.2)
The symbols
1
lim
and lim are also denoted by ‘lim inf’ and ‘lim sup.’
Sometimes the D’Alembert ratio test is easier to apply than the Cauchy root test. It is given
as follows: the sum in Eq. (11.1) has the radius of convergence R if and only if
1
R
= lim
n→∞
f
n+1
f
n
, (11.3)
whenever the limit exists.
When the radius of convergence for the generating function is known, we have a rough esti-
mate of the coefficients:
Theorem 11.2 Let the ordinary generating function f (z) of the sequence {f
n
} converge in
the circle |z| < R, but diverge for some point on the boundary |z| = R; then for any
ε
> 0
f
n
= O((R −
ε
)
−n
). (11.4)
Notes: (a) When all the coefficients are positive, which is usually the case in calculations
that result from analysis of algorithms, the smallest singularity will be at the real value z = R.
(b) The fact that the series diverges on the boundary also says that the coefficients are
bounded from below by (R +
ε
)
−n
, that is, f
n
= Ω((R +
ε
)
−n
).
Recall that a function f (z) is regular in the domain D if and only if it is differentiable in the
domain D. A complex-valued function is said to be an entire function if it is holomorphic
everywhere on the whole complex plane (that is, at all finite points). The functions sin z
and e
z
are examples of an entire function, but (1 −z)
−1
is not because it has a singularity at
1
The usual names for lim
f
n
and lim f
n
, without the absolute value operator, are the lower and upper limits of
the sequence. The definition of the lower limit says that it is t he largest number which i s smaller than all but a
finite number of f
n
(or smaller than all f
n
, n > n
0
). The upper limit is defined accordingly. If they are equal, the
sequence is simply said to have a limit, denoted by lim f
n
.
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.
