LINEBURG

 << Пред. стр. страница 10(всего 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  contains an extended discussion of the relations between diп¬Ђerent
Tauberian theorems and of the necessity for various conditions.

69
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  is an
introductory survey to some recurrence methods.
WimpвЂ™s book  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
 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 .) 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

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

G(z)
f (z) = , (9.1)
h(z)

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 . Dividing G(z) by
h(z) we obtain
g(z)
f (z) = p(z) + , (9.2)
h(z)
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
z
h(z) = h(0) 1в€’ , (9.3)
zj
j=1

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 ,
mj
d
cj,k
f (z) = p(z) +
(1 в€’ z/zj )k
j=1 k=1
mj
d в€ћ
h + k в€’ 1 h в€’h
= p(z) + cj,k z zj . (9.4)
kв€’1
j=1 k=1 h=0

Thus
mj
d
h + k в€’ 1 в€’n
an = [z n ]p(z) + cj,k zj . (9.5)
kв€’1
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 , but are unwieldy and
seldom used.

Example 9.1. Fibonacci numbers. As was noted in Example 6.3,
в€ћ
z
Fn z n =
F (z) = .
1 в€’ z в€’ z2
n=0

Now
h(z) = 1 в€’ z в€’ z 2 = (1 + П†в€’1 z)(1 в€’ П†z) , (9.7)

71
where П† = (1 + 51/2 )/2 is the golden ratio. Therefore

1 1 1
F (z) = в€љ в€’ (9.8)
1 в€’ П†z 1 + П†в€’1 z
5
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)
|z|=R

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)

72
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
n
в‰¤ 100(0.55)kв€’n + 40(0.55)в€’n |h (ПЃ)|в€’1
[z ]FA (z) +
h (ПЃ)
(9.14)
в‰¤ 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)
(9.16)
= в€’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)

and
ПЃв€’n = 2n exp(в€’n(2k CA (1/2))в€’1 + O(nk2в€’2k )) . (9.18)

Therefore
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

73
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 .)
For other methods and results in this area, see .
В

Inhomogeneous recurrences with constant coeп¬ѓcients, say,
d
an = ci anв€’i + bn , nв‰Ґd, (9.20)
i=1

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  that t 1 = t2 = 1 and
that
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)!
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)

74
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
(1 в€’ w)в€’1 exp(в€’(1 в€’ w)в€’1 )dw
t(z) = (1 в€’ z) exp((1 в€’ z) ) C+ , (9.24)
z

where
1
в€’1
(1 в€’ w)в€’1 exp(в€’(1 в€’ w)в€’1 )dw = 0.148495 . . . .
C=e в€’ (9.25)
0

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
(1 в€’ w)в€’1 exp(в€’(1 в€’ w)в€’1 )dw
(1 в€’ z) exp((1 в€’ z) ) (9.27)
z

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
r
an = cj (n)anв€’j , nв‰Ґr , (9.29)
j=1

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

75
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)
n=1

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
r
cj (n)z j ,
1в€’ (9.32)
j=1

76
and therefore is often a root of
r
lim cj (n) z j .
1в€’ (9.33)
nв†’в€ћ
j=1

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
e

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 .
(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
n
(в€’1)k
n
an = , n = 0, 1, . . . . (9.36)
k k!
k=0

77
 << Пред. стр. страница 10(всего 24)ОГЛАВЛЕНИЕ След. стр. >>