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 [212] 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 [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

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 [205]. 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 [175], 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 [236].)
For other methods and results in this area, see [18].
Ā

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 [120] 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 [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
n
(ā’1)k
n
an = , n = 0, 1, . . . . (9.36)
k k!
k=0

77
 << Ļšåä. ńņš. ńņšąķčöą 10(āńåćī 24)ĪĆĖĄĀĖÅĶČÅ Ńėåä. ńņš. >>