LINEBURG

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

has the property that bn /bnвҲ’1 is a rational function of n, and if it is, it gives an explicit form
for bn . We note that if bn /bnвҲ’1 is a rational function of n, then so is

an bn /bnвҲ’1 вҲ’ 1
= . (3.4)
anвҲ’1 1 вҲ’ bnвҲ’2 /bnвҲ’1

Therefore GosperвҖ™s algorithm should be applied only when a n /anвҲ’1 is rational.
The other recent development is the Wilf-Zeilberger method for proving combinatorial
identities [379, 380]. Given a conjectured identity, it provides an algorithmic procedure for
verifying it. This method succeeds in a surprisingly wide range of cases. Typically, to prove
an identity of the form
U (n, k) = S(n) , nвүҘ0, (3.5)
k

10
where S(n) = 0, Wilf and Zeilberger deп¬Ғne F (n, k) = U (n, k)/S(n) and search for a rational
function R(n, k) such that if G(n, k) = R(n, k)F (n, k вҲ’ 1), then

F (n + 1, k) вҲ’ F (n, k) = G(n, k + 1) вҲ’ G(n, k) (3.6)

holds for all integers n, k with n вүҘ 0, and such that

1) for each integer k, the limit
fk = lim F (n, k) (3.7)
nвҶ’вҲһ

exists and is п¬Ғnite.

2) for each integer n вүҘ 0, limkвҶ’В±вҲһ G(n, k) = 0.

вҲһ
3) limkвҶ’вҲ’вҲһ G(n, k) = 0.
n=0

If all these conditions are satisп¬Ғed, and Eq. (3.5) holds for n = 0, then it holds for all n вүҘ 0.

Example 3.1. DixonвҖ™s binomial sum identity. This identity states that

n+b b+c n+c (n + b + c)!
(вҲ’1)k = . (3.8)
n+k b+k c+k n! b! c!
k

This can be proved by the Wilf-Zeilberger method by taking

(b + 1 вҲ’ k)(c + 1 вҲ’ k)
R(n, k) = (3.9)
2(n + k)(n + b + c + 1)

and verifying that the conditions above hold.
В

The Wilf-Zeilberger method requires п¬Ғnding a rational function R(n, k) that satisп¬Ғes the
properties listed above. This is often hard to do, especially by hand. GosperвҖ™s algorithm leads
to a systematic procedure for constructing such R(n, k).

To conclude this section, we mention that a useful resource when investigating sequences
arising in combinatorial settings is the book of Sloane [345, 346], which lists several thousand
sequences and gives references for them. Section 17 mentions some software systems that are
useful in asymptotics.

11
4. Basic estimates: factorials and binomial coeп¬ғcients

No functions in combinatorial enumeration are as ubiquitous and important as the facto-
rials and the binomial coeп¬ғcients. In this section we state some estimates for these quantities,
which will be used throughout this chapter and are of widespread applicability. Several diп¬Җerent
proofs of some of these estimates will be sketched later.
The basic estimate, from which many others follow, is that for the factorial. As was
mentioned in the introduction, the basic form of StirlingвҖ™s formula is

n! вҲј (2ПҖn)1/2 nn eвҲ’n as nвҶ’вҲһ. (4.1)

This is suп¬ғcient for many enumeration problems. However, when necessary one can draw on
much more accurate estimates. For example Eq. 6.1.38 in  gives

n! = (2ПҖn)1/2 nn exp(вҲ’n + Оё/(12n)) (4.2)

for all n вүҘ 1, where Оё = Оё(n) satisп¬Ғes 0 < Оё < 1. More generally, there is StirlingвҖ™s asymptotic
expansion:
1 1
log{n!(2ПҖn)вҲ’1/2 nвҲ’n en } вҲј вҲ’ + В·В·В· . (4.3)
12n 360n3
(This is an asymptotic series in the sense of Eq. (2.2), and there is no convergent expansion
for log{n!(2ПҖn)вҲ’1/2 nвҲ’n en } as a power series in nвҲ’1 .) Further terms in the expansion (4.3)
can be obtained, and they involve Bernoulli numbers. In most references, such as Eq. 6.1.37
or 6.1.40 of , StirlingвҖ™s formula is presented for О“(x), where О“ is EulerвҖ™s gamma function.
Expansions for О“(x) translate readily into ones for n! because n! = О“(n + 1).
StirlingвҖ™s approximation yields the expansion

4n
2n 1 1 5
+ O(nвҲ’4 )
= 1вҲ’ + + . (4.4)
2 3
(ПҖn)1/2
n 8n 128n 1024n

A less precise but still useful estimate is
1/2
n 2
2n
вҲј as nвҶ’вҲһ. (4.5)
n/2 ПҖn
n n
This estimate is used frequently. The binomial coeп¬ғcients are symmetric, so that =
k nвҲ’k
n
and unimodal, so that for a п¬Ғxed n and k varying, the increase monotonically up to a peak
k

at k = n/2 (which is unique for n even and has two equal high points at k = (n В± 1)/2 for
n odd) and then decrease.

12
More important than Eq. (4.5) are expansions for general binomial coeп¬ғcients. Eq. (4.2)
shows that for 1 вү¤ k вү¤ n вҲ’ 1,
1/2
nn
n n! n 1 1
= = exp O +
k k (n вҲ’ k)nвҲ’k
k k!(n вҲ’ k)! 2ПҖk(n вҲ’ k) k nвҲ’k
1/2
n k 1 1
= exp nH +O + , (4.6)
2ПҖk(n вҲ’ k) n k nвҲ’k

where
H(x) = вҲ’x log x вҲ’ (1 вҲ’ x) log(1 вҲ’ x) (4.7)

is the entropy function. (We set H(0) = H(1) = 0 to make H(x) continuous for 0 вү¤ x вү¤ 1.)
Simplifying further, we obtain

n
= exp(nH(k/n) + O(log n)) , (4.8)
k

an estimate that is valid for all 0 вү¤ k вү¤ n. In many situations it suп¬ғces to use the weaker but
simpler bound
n ne k
вү¤ , 0вү¤kвү¤n. (4.9)
k k
Approximations of this form are used frequently in information theory and other п¬Ғelds.
A general estimate that can be derived by totally elementary methods, without recourse
to StirlingвҖ™s formula, is
вҲ’1
n n
= exp(вҲ’2(k вҲ’ n/2)2 /n + O(|k вҲ’ n/2|3 /n2 )) , (4.10)
k n/2

valid for |k вҲ’ n/2| вү¤ n/4, say. It is most useful for |k вҲ’ n/2| = o(n 2/3 ), since the error term is
small then. Similarly,
r
n n nвҲ’k
вҲј as nвҶ’вҲһ, (4.11)
k+r k k

uniformly in k provided r (which may be negative) satisп¬Ғes r 2 = o(k) and r 2 = o(n вҲ’ k).
Further, we have
(n + k)! вҲј nk exp(k 2 /(2n))n! as nвҶ’вҲһ, (4.12)

again uniformly in k provided k = o(n 2/3 ).

5. Estimates of sums and other basic techniques

When encountering a combinatorial sum, the п¬Ғrst reaction should always be to check
whether it can be simpliп¬Ғed by use of some identity. If no identity for the sum is found, the

13
next step should be to try to transform the problem to eliminate the sum. Usually we are
interested not in single isolated sums, but parametrized families of them, such as

bn = an (k) , (5.1)
k

and it is the asymptotic behavior of the b n as n вҶ’ вҲһ that is desired. A standard and well-
known technique (named the вҖңsnake-oilвҖқ method by Wilf ) for handling such cases is to
form a generating function f (z) for the b n , use the properties of the an (k) to obtain a simple
form for f (z), and then obtain the asymptotics of the b n from the properties of f (z). This
method will be presented brieп¬‚y in Section 6. In this section we discuss what to do if those
two approaches fail. Sometimes the methods to be discussed can also be used in a preliminary
phase to obtain a rough estimate for the sum. This estimate can then be used to decide which
identities might be true, or what generating functions to form.
There are general methods for dealing with sums (cf. ), many of which are used in
asymptotic enumeration. A basic technique of this type is summation by parts. Often sums
to be evaluated can be expressed as
n вҲһ
aj bj or aj bj ,
j=1 j=1

where the bj , say, are known explicitly or behave smoothly, while the a j by themselves might
not be known well, but the asymptotics of
k
A(k) = aj (5.2)
j=1

are known. Summation by parts relies on the identity
n nвҲ’1
aj bj = A(k)(bk вҲ’ bk+1 ) + A(n)bn . (5.3)
j=1 k=1

Example 5.1. Sum of primes. Let
Sn = p, (5.4)
pвү¤n

where p runs over the primes вү¤ n. The Prime Number Theorem  states that the function

ПҖ(x) = 1 (5.5)
pвү¤x

14
satisп¬Ғes
x
ПҖ(x) вҲј as xвҶ’вҲһ. (5.6)
log x
(More precise estimates are available, but we will not use them.) We rewrite
n
Sn = aj bj , (5.7)
j=1

where пЈ±
пЈІ1 j is prime ,
aj = (5.8)
0 otherwise ,
пЈі

and bj = j for all j. Then A(k) = ПҖ(k) and summation by parts yields
nвҲ’1
Sn = вҲ’ПҖ(k) + ПҖ(n)n . (5.9)
k=1

Since
nвҲ’1 nвҲ’1
n2
k
ПҖ(k) вҲј вҲј as n вҶ’ вҲһ , (5.10)
log k 2 log n
k=1 k=2
we have
n2
Sn вҲј as nвҶ’вҲһ. (5.11)
2 log n
В

Summation by parts is used most commonly in situations like those of Example 5.1, to
obtain an estimate for one sum from that of another.
Summation by parts is often easiest to carry out, both conceptually and notationally, by
using integrals. If we let
A(x) = ak , (5.12)
kвү¤x

then A(x) = A(n) for n вү¤ x < n + 1. Suppose that b k = b(k) for some continuously diп¬Җeren-
tiable function b(x). Then
k+1
bk вҲ’ bk+1 = вҲ’ b (x)dx , (5.13)
k
and we can rewrite Eq. (5.3) as
n n
aj bj = A(n)b(n) вҲ’ A(x)b (x)dx . (5.14)
1
j=1

(One can apply similar formulas even when the b j are not smooth, but this usually requires
Riemann-Stieltjes integrals, cf. .) The approximation of sums by integrals that appears in
(5.14) is common, and will be treated at length later.

15
5.1. Sums of positive terms

Sums of positive terms are extremely common. They can usually be handled with only a
few basic tools. We devote substantial space to this topic because it is important and because
the simplicity of the methods helps in illustrating some of the basic principles of asymptotic
estimation, such as approximation by integrals, neglecting unimportant terms, and uniform
convergence. For readers not familiar with asymptotic methods, working through the examples
of this section is a good exercise that will make it easier to learn other techniques later.
Typical sums are of the form

bn = an (k) , an (k) вүҘ 0 , (5.15)
k

where k runs over some range of summation, often 0 вү¤ k вү¤ n or 0 вү¤ k < вҲһ, and the
an (k) may be given either explicitly or only through an asymptotic approximation. What
is desired is the asymptotic behavior of b n as n вҶ’ вҲһ. Usually the an (k) for n п¬Ғxed are
unimodal, so that either i) an (k) вү¤ an (k + 1) for all k in the range, or ii) an (k) вүҘ an (k + 1)
for all k, or iii) an (k) вү¤ an (k + 1) for k вү¤ k0 , and an (k) вүҘ an (k + 1) for k > k0 . The
single most important task in estimating b n is usually to п¬Ғnd the maximal an (k). This can be
done either by combinatorial means (involving knowledge of where the a n (k) come from), by
asymptotic estimation of the an (k), or (most common when the an (k) are expressed in terms
of factorials or binomial coeп¬ғcients) by п¬Ғnding where the ratio a n (k + 1)/an (k) is close to 1.
If an (k + 1)/an (k) < 1 for all k, then we are in case ii) above, and if a n (k + 1)/an (k) > 1 for
all k, we are in case i). If there is a k 0 in the range of summation such that a n (k0 + 1) is close
to an (k0 ), then we are almost certainly in case iii) and the peak occurs at some k close to k 0 .
The diп¬Җerent cases are illustrated in the examples presented later in this section.
Once max an (k) = an (k0 ) has been found, the next task is to show that most of the terms
in the sum are insigniп¬Ғcant. For example, if the sum in Eq. (5.15) is over 0 вү¤ k вү¤ n, and if
an (0) = 1 is the largest term, then
n
an (k) < nвҲ’1 ,
k=0
an (k)<nвҲ’2

which is negligible if we are only after a rough approximation to b n , say of the form bn вҲј cn
as n вҶ’ вҲһ, or even bn = cn (1 + O(nвҲ’1 )) as n вҶ’ вҲһ. Once the small terms have been
discarded, we are usually left with a short range of summation. It can happen that this range

16
is extremely short, and the maximal term a n (k0 ) is much larger than any of its neighbors to
the extent that bn вҲј an (k0 ) as n вҶ’ вҲһ. More commonly, the number of terms that contribute
signiп¬Ғcantly to bn does grow as n вҶ’ вҲһ, but slowly. Their contribution, relative to that of the
maximal term an (k0 ), can usually be estimated by some simple function of k вҲ’ k 0 , and the sum
of all of them approximated by an explicit integral. This method is sometimes referred to as
LaplaceвҖ™s method for sums (in analogy to LaplaceвҖ™s method for estimating integrals, mentioned
in Section 5.5, which proceeds in a similar spirit). There is extensive discussion of this method
in .

Example 5.2. Sums of the partition function. We estimate
n
p(k)k ,
Un = (5.16)
k=1

where p(k) is the number of partitions of k. Since any partition of m вҲ’ 1, say one with c j parts
of size j, can be transformed into a partition of m with c 1 + 1 parts of size 1, and cj of size
j for j вүҘ 2, we have p(m) вүҘ p(m вҲ’ 1) for all m вүҘ 2. Therefore the largest term in the sum
in (5.16) is the one with k = n. If the only estimate for p(k) that we have is the one given by
(1.6), then
p(n)n = exp(Cn3/2 вҲ’ n log(4 В· 31/2 n) + O(n1/2 )) . (5.17)

Since the constant implied by the O-symbol is not speciп¬Ғed, this estimate is potentially larger
than p(n)n by a factor of exp(cn1/2 ), so we can only obtain asymptotics of log p(n) n , not
of p(n)n itself. This also means that rough estimates of U n follow easily from (5.17). Since
p(k)k вү¤ p(n)n for all k < n, and there are n terms in the sum, we have p(n) n вү¤ Un вү¤ np(n)n ,
and because of the large error term in (5.17), we obtain

Un = exp(Cn3/2 вҲ’ n log(4 В· 31/2 n) + O(n1/2 )) . (5.18)

Thus the use of the poor estimate (1.6) for p(n) means that we can obtain only a crude estimate
for Un , and there is no need for careful analysis.
Instead of (1.6) we can use the more reп¬Ғned estimate (1.5). Let q n denote п¬Ғrst term on the
right side of (1.5). Then we have

p(n) = qn + O(nвҲ’1 exp(Cn1/2 /2)) = qn (1 + O(exp(вҲ’Cn1/2 /2))) , (5.19)

so
p(n)n = qn (1 + O(n exp(вҲ’Cn1/2 /2))) = qn (1 + O(exp(вҲ’Cn1/2 /3))) ,
n n
(5.20)

17
say. Also, for some > 0 we п¬Ғnd from Eq. (1.5) (or Eq. 1.6) that for large n

qnвҲ’1 < qn вҲ’ nвҲ’1/2 qn .

Thus for large n,
nвҲ’1
qnвҲ’1 < qn (1 вҲ’ nвҲ’1/2 )nвҲ’1
nвҲ’1

< qn exp(вҲ’ n1/2 /2) ,
n

and therefore
nвҲ’1
p(k)k вү¤ (n вҲ’ 1)p(n вҲ’ 1)nвҲ’1 < qn exp(вҲ’ n1/2 /3) .
n

k=1
Thus we obtain
Un = qn (1 + O(exp(вҲ’Оҙn1/2 )))
n
(5.21)

for some Оҙ > 0.
The estimates of Un presented above relied on the observation that the last term in the sum
(5.16) deп¬Ғning Un is much larger than the sum of all the other terms. This does not happen
often. A more typical example is presented by
n
 << Пред. стр. страница 2(всего 24)ОГЛАВЛЕНИЕ След. стр. >>