<< . .

( 24)

. . >>

Sections 10“12. Only behavior of the generating functions Π(1 ’ z »j )’1 or Π(1 + z »j ) in an
angle |Arg|(1 ’ z)| ¤ π/2 ’ δ for some δ > 0 needs to be controlled.
Ingham™s paper [212] contains an extended discussion of the relations between di¬erent
Tauberian theorems and of the necessity for various conditions.

9. Recurrences

This section presents some basic methods for handling recurrences. The title is slightly
misleading, since almost all of this chapter is devoted to methods that are useful in this area.
Almost all asymptotic estimation problems concern quantities that are de¬ned through implicit
or explicit recurrences. Furthermore, the most common and most e¬ective method of solving
recurrences is often to determine its generating function and then apply the methods presented
in the other sections. However, there are many recurrences, and those discussed in Sections 9.4
and 9.5 require special methods that do not ¬t into other sections. These methods deserve to
be included, so it seems preferable to explain them after treating some of the more common
types of recurrences, even though those could have been covered elsewhere in this chapter.
Since generating functions are the most powerful tool for handling combinatorial recur-
rences, all the books listed in Section 18 that help in dealing with combinatorial identities and
generating functions are also useful in handling recurrences. Methods for recurrences that are
not amenable to generating function methods are presented in [175, 177]. Lueker [264] is an
introductory survey to some recurrence methods.
Wimp™s book [382] is concerned primarily with numerical stability problems in computing
with recurrences. Such problems are important in computing values of orthogonal polynomials,
for example, but seldom arise in combinatorial enumeration. However, there are sections of
[382] that are relevant to our topic, for example to the discussion of di¬erential equations in
Section 9.2.

9.1. Linear recurrences with constant coe¬cients

The most famous sequence that satis¬es a linear recurrence with constant coe¬cients is
that of the Fibonacci numbers, de¬ned by F 0 = F1 = 1, Fn = Fn’1 +Fn’2 for n ≥ 2. There are
many others that are only slightly less well known. Fortunately, the theory of such sequences
is well developed, and from the standpoint of asymptotic enumeration their behavior is well
understood. (For a survey of number theoretic results, together with a list of many unsolved
problems about such sequences that arise in that area, see [73].) There are even several di¬erent
approaches to solving linear recurrences with constant coe¬cients. The one we emphasize here
is that of generating functions, since it ¬ts in best with the rest of this chapter. For other
approaches, see [287, 298], for example.
Suppose that we have a linear recurrence or a system of recurrences and have found that

the generating function f (z) we are interested in has the form

f (z) = , (9.1)

where G(z) and h(z) are polynomials. The basic tool for obtaining asymptotic information
about [z n ]f (z) is the partial fraction expansion of a rational function [205]. Dividing G(z) by
h(z) we obtain
f (z) = p(z) + , (9.2)
where p(z), g(z), and h(z) are all polynomials in z and deg g(z) < deg h(z). We can assume
that h(0) = 0, since if that were not the case, we would have g(0) = 0 (as in the opposite case
f (z) would not be a power series in z, but would have terms such as z ’1 or z ’2 ) and we could
cancel a common factor of z from g(z) and h(z). Therefore, if d = deg h(z), we can write
d mj
h(z) = h(0) 1’ , (9.3)

where zj , 1 ¤ j ¤ d are the distinct roots of h(z) = 0, zj has multiplicity mj ≥ 1, and
mj = d. Hence we ¬nd [175, 205] that for certain constants c j,k ,
f (z) = p(z) +
(1 ’ z/zj )k
j=1 k=1
d ∞
h + k ’ 1 h ’h
= p(z) + cj,k z zj . (9.4)
j=1 k=1 h=0

h + k ’ 1 ’n
an = [z n ]p(z) + cj,k zj . (9.5)
j=1 k=1

When mj = 1,
’g(zj )
cj,1 = , (9.6)
zj h (zj )
and explicit formulas for the cj,k when mj > 1 can also be derived [175], but are unwieldy and
seldom used.

Example 9.1. Fibonacci numbers. As was noted in Example 6.3,

Fn z n =
F (z) = .
1 ’ z ’ z2

h(z) = 1 ’ z ’ z 2 = (1 + φ’1 z)(1 ’ φz) , (9.7)

where φ = (1 + 51/2 )/2 is the golden ratio. Therefore

1 1 1
F (z) = √ ’ (9.8)
1 ’ φz 1 + φ’1 z
and for n ≥ 0,
Fn = [z n ]F (z) = 5’1/2 (φn ’ (’φ)’n ) . (9.9)

The partial fraction expansion (9.4) shows that the ¬rst-order asymptotics of sequence a n
satisfying a linear recurrence of the form (6.30) are determined by the smallest zeros of the
characteristic polynomial h(z). The full asymptotic expansion is given by (9.5), and involves
all the zeros. In practice, using (9.5) presents some di¬culties, in that multiplicities of zeros
are not always easy to determine, and the coe¬cients c j,k are often even harder to deal with.
Eventually, for large n, their in¬‚uence becomes negligible, but when uniform estimates are
required they present a problem. In such cases the following theorem is often useful.

Theorem 9.1. Suppose that f (z) = g(z)/h(z), where g(z) and h(z) are polynomials, h(0) =
0, deg g(z) < deg h(z), and that the only zeros of h(z) in |z| < R are ρ 1 , . . . , ρk , each of
multiplicity 1. Suppose further that

max |f (z)| ¤ W , (9.10)

and that R ’ |ρj | ≥ δ for some δ > 0 and 1 ¤ j ¤ k. Then

k k
g(ρj ) ’n’1
[z n ]f (z) + ¤ W R’n + δ ’1 R’n
ρj |g(ρj )/h (ρj )| . (9.11)
h (ρj )
j=1 j=1

Theorem 9.1 is derived using methods of complex variables, and a proof is sketched in
Section 10. That section also discusses how to locate all the zeros ρ 1 , . . . , ρk of a polynomial
h(z) in a disk |z| < R. In general, the zero location problem is not a serious one in enumeration
problems. Usually there is a single positive real zero that is closer to the origin than any other,
it can be located accurately by simple methods, and R is chosen so that |z| < R encloses only
that zero.

Example 9.2. Sequences with forbidden subblocks. We continue with the problem presented
in Examples 6.4 and 6.8. Both FA (z) and GA (z) have as denominators

h(z) = z k + (1 ’ 2z)CA (z) , (9.12)

which is a polynomial of degree exactly k. Later, in Example 10.6, we will show that for k ≥ 9,
h(z) has exactly one zero ρ in |z| ¤ 0.6, and that for |z| = 0.55, |h(z)| ≥ 1/100. Furthermore,
by Example 6.7, ρ ’ 1/2 as k ’ ∞. On |z| = 0.55,

|FA (z)| ¤ 100 · (0.55)k . (9.13)

Theorem 9.1 then shows, for example, that for n > k ≥ k 0 ,

CA (ρ)ρ’n’1
¤ 100(0.55)k’n + 40(0.55)’n |h (ρ)|’1
[z ]FA (z) +
h (ρ)
¤ 50(0.55)’n ,

since by Example 6.7, as k ’ ∞,

h (ρ) = kρk’1 ’ 2CA (ρ) + (1 ’ 2ρ)CA (ρ) ∼ ’2CA (ρ) ∼ ’ρ’1 . (9.15)

The estimate (9.14), when combined with the expansions of Example 6.7, gives accurate
approximations for pn , the probability that A does not appear as a block among the ¬rst n
coin tosses. We have
pn = 2’n [z n ]Fz (z)
= ’2’n CA (ρ)ρ’n’1 (h (ρ))’1 + O(exp(’0.09n)) .

We now estimate h (ρ) as before, in (9.15), but more carefully, putting in the approximation
for ρ from Example 6.7. We ¬nd that

h (ρ) = ’ρ’1 + O(k2’k ) , (9.17)

ρ’n = 2n exp(’n(2k CA (1/2))’1 + O(nk2’2k )) . (9.18)

pn = exp(’n(2k CA (1/2))’1 + O(nk2’2k )) + O(exp(’n/12)) . (9.19)

This shows that pn has a sharp transition. It is close to 1 for n = o(2 k ), and then, as
n increases through 2k , drops rapidly to 0. (The behavior on the two sides of 2 k is not
symmetric, as the drop towards 0 beyond 2 k is much faster than the increases towards 1
on the other side.) For further results and applications of such estimates, see [180, 181].
Estimates such as (9.19) yield results sharper than those of Example 6.8. They also prove (see

Example 14.1) that the expected lengths of the longest run of 0™s in a random sequence of
length n is log 2 n + u(log 2 n) + o(1) as n ’ ∞, where u(x) is a continuous function that is not
constant and satis¬es u(x + 1) = u(x). (See also the discussion of carry propagation in [236].)
For other methods and results in this area, see [18].

Inhomogeneous recurrences with constant coe¬cients, say,
an = ci an’i + bn , n≥d, (9.20)

are not covered by the techniques discussed above. One can still use the basic generating
function approach to derive the ordinary generating function of a n , but this time it is in terms
of the ordinary generating function of b n . If bn does not grow too rapidly, the “subtraction of
singularities” method of Section 10.2 can be used to derive the asymptotics of a n in a form
similar to that given by (9.26).

9.2. Linear recurrences with varying coe¬cients

Linear recurrences with constant coe¬cients have a nice and complete theory. That is no
longer the case when one allows coe¬cients that vary with the index. This is not a fault of
mathematicians in not working hard enough to derive elegant results, but re¬‚ects the much
more complicated behavior that can occur. The simplest case is when the recurrence has a
¬nite number of terms, and the coe¬cients are polynomials in n.

Example 9.3. Two-sided generalized Fibonacci sequences. Let t n be the number of integer
sequences (bj , . . . , b2 , b1 , 1, 1, a1 , a2 , . . . , ak ) with j + k + 2 = n in which each bi is the sum of
one or more contiguous terms immediately to its right, and each a i is likewise the sum of one
or more contiguous terms immediately to its left. It was shown in [120] that t 1 = t2 = 1 and
tn+1 = 2ntn ’ (n ’ 1)2 tn’1 for n≥2. (9.21)

If we let

tn z n’1
t(z) = (9.22)
(n ’ 1)!

be a modi¬ed exponential generating function, then the recurrence (9.21) shows that

t (z)(1 ’ z)2 ’ t(z)(2 ’ z) = 1 . (9.23)

Standard methods for solving ordinary di¬erential equations, together with the initial condi-
tions t1 = t2 = 1, then yield the explicit solution
’1 ’1
(1 ’ w)’1 exp(’(1 ’ w)’1 )dw
t(z) = (1 ’ z) exp((1 ’ z) ) C+ , (9.24)

(1 ’ w)’1 exp(’(1 ’ w)’1 )dw = 0.148495 . . . .
C=e ’ (9.25)

Once the explicit formula (9.24) for t(z) is obtained, the methods of Section 12 give the estimate

tn ∼ C(n ’ 1)!(e/π)1/2 exp(2n1/2 )(2n1/4 )’1 as n’∞. (9.26)

It is easy to show that the absolute value of
’1 ’1
(1 ’ w)’1 exp(’(1 ’ w)’1 )dw
(1 ’ z) exp((1 ’ z) ) (9.27)

is small for |z| < 1. Therefore the asymptotics of the t n are determined by the behavior of
coe¬cients of
C(1 ’ z)’1 exp((1 ’ z)’1 ) , (9.28)

and that can be obtained easily. The estimate (9.26) then follows.

To see just how di¬erent the behavior of linear recurrences with polynomial coe¬cients can
be from those with constant coe¬cients, compare the behavior of the sequences in Example 9.3
above and Example 9.4 (given below). The existence of such di¬erences should not be too
surprising, since after all even the ¬rst order recurrence a n = nan’1 for n ≥ 2, a1 = 1, has the
obvious solution an = n!, which is not at all like the solutions to constant coe¬cient recurrences.
However, when an = nan’1 , a simple change of variables, namely a n = bn n!, transforms this
recurrence into the trivial one of b n = bn’1 = · · · = b1 = 1 for all n. Such rescaling is among
the most fruitful methods for dealing with nonlinear recurrences, even though it is seldom as
simple as for an = n!.
Example 9.3 is typical in that a sequence satisfying a linear recurrence of the form
an = cj (n)an’j , n≥r , (9.29)

where r is ¬xed and the cj (n) are rational functions (a P -recursive sequence in the notation
of Section 6.3) can always be transformed into a di¬erential equation for a generating func-
tion. Whether anything can be done with that generating function depends strongly on the

recurrence and the form of the generating function. Example 9.3 is atypical in that there is an
explicit solution to the di¬erential equation. Further, this explicit solution is a nice analytic
function. This is due to the special choice of the form of the generating function. An expo-
nential generating function seems natural to use in that example, since the recurrence (9.21)
shows immediately that tn ¤ (2n ’ 2)(2n ’ 4) . . . 2 = 2n’1 (n ’ 1)!, and a slightly more involved
induction proves that tn grows at least as fast as a factorial. If we tried to use an ordinary
generating function

tn z n ,
u(z) = (9.30)

then the recurrence (9.21) would yield the di¬erential equation

z 4 u (z) + z 3 u (z) + (1 ’ 2z 2 )u(z) = z ’ z 2 , (9.31)

which is not as tractable. (This was to be expected, since u(z) is only a formal power series.)
Even when a good choice of generating function does yield an analytic function, the di¬erential
equation that results may be hard to solve. (One can always ¬nd a generating function that
is analytic, but the structure of the problem may not be re¬‚ected in the resulting di¬erential
equation, and there may not be anything nice about it.)
There is an extensive literature on analytic solutions of di¬erential equations
(cf. [205, 206, 207, 272, 368, 372]), but it is not easy to apply in general. Singularities of
analytic functions that satisfy linear di¬erential equations with analytic coe¬cients are usu-
ally of only a few basic forms, and so the methods of Sections 11 and 12 su¬ce to determine
the asymptotic behavior of the coe¬cients. The di¬culty is in locating the singularities and
determining their nature. We refer to [206, 207, 272, 368, 372] for methods for dealing with
this di¬culty, since they are involved and so far have been seldom used in combinatorial enu-
meration. There will be some further discussion of di¬erential equations in Section 15.3.
Some aspects of the theory of linear recurrences with constant coe¬cients do carry over
to the case of varying coe¬cients, even when the coe¬cients are not rational functions. For
example, there will in general be r linearly independent solutions to the recurrence (9.29)
(corresponding to the di¬erent starting conditions). Also, if a solution a n has the property
that an+1 /an tends to a limit ± as n ’ ∞, then 1/± is a limit of zeros of
cj (n)z j ,
1’ (9.32)

and therefore is often a root of
lim cj (n) z j .
1’ (9.33)

Whether there are exactly r linearly independent solutions is a di¬cult problem. Extensive
research was done on this topic 1920™s and 1930™s [2, 29], culminating in the work of Birkho¬
and Trjitzinsky [51, 52, 53, 366, 367]. This work applies to recurrences of the form (9.29) where
the cj (n) have Poincar´ asymptotic expansions

cj (n) ∼ nkj /k {cj,0 + cj,1 n’1/k + cj,2 n’2/k + · · ·} as n’∞, (9.34)

where the kj and k are integers and cj,0 = 0 if cj (n) is not identically 0 for all n. It follows from
this work that solutions to the recurrence are expressible as linear combinations of elements of
the form
(n!)p/q exp(P (n1/m ))n± (log n)h , (9.35)

where h, m, p, and q are integers, P (z) a polynomial, and ± a complex number. An exposition
of this theory and how it applies to enumeration has been given by Wimp and Zeilberger [384].
(There is a slight complication in that most of the literature cited above is concerned with
recurrences for functions of a real argument, not sequences, but this is not a major di¬culty.)
There is still a problem in identifying which linear combination provides the derived solution.
Wimp and Zeilberger point out that it is usually easy to show that the largest of the terms
of the form (9.35) does show up with a nonzero coe¬cient, and so determines the asymptotics
of an up to a multiplicative constant. However, the Birkho¬-Trjitzinsky method does not in
general provide any techniques for determining that constant.
The major objection to the use of the Birkho¬-Trjitzinsky results is that they may not be
rigorous, since gaps are alleged to exist in the complicated proofs [211, 383]. Furthermore, in
almost all combinatorial enumeration applications the coe¬cients are rational, and so one can
use the theory of analytic di¬erential equations.
When there is no way to avoid linear recurrences with coe¬cients that vary but are not
rational, one can sometimes use the work of Kooman [243, 244], which develops the theory of
second order linear recurrences with almost-constant coe¬cients.

Example 9.4. An oscillating sequence. Let
an = , n = 0, 1, . . . . (9.36)
k k!


<< . .

( 24)

. . >>

Copyright Design by: Sunlight webdesign