LINEBURG

ńņšąķčöą 10 |

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 |

Copyright © Design by: Sunlight webdesign