<< . .

( 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)

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)

exists and is ¬nite.

2) for each integer n ≥ 0, limk’±∞ G(n, k) = 0.

3) limk’’∞ G(n, k) = 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!

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.

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 [297] 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
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 [297], 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

2n 1 1 5
+ O(n’4 )
= 1’ + + . (4.4)
2 3
n 8n 128n 1024n

A less precise but still useful estimate is
n 2
∼ 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
and unimodal, so that for a ¬xed n and k varying, the increase monotonically up to a peak

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.

More important than Eq. (4.5) are expansions for general binomial coe¬cients. Eq. (4.2)
shows that for 1 ¤ k ¤ n ’ 1,
n n! n 1 1
= = exp O +
k k (n ’ k)n’k
k k!(n ’ k)! 2πk(n ’ k) k n’k
n k 1 1
= exp nH +O + , (4.6)
2πk(n ’ k) n k n’k

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

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

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
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,
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

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)

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 [377]) 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. [234]), 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
A(k) = aj (5.2)

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)

where p runs over the primes ¤ n. The Prime Number Theorem [23] states that the function

π(x) = 1 (5.5)

π(x) ∼ as x’∞. (5.6)
log x
(More precise estimates are available, but we will not use them.) We rewrite
Sn = aj bj , (5.7)

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
Sn = ’π(k) + π(n)n . (5.9)

n’1 n’1
π(k) ∼ ∼ as n ’ ∞ , (5.10)
log k 2 log n
k=1 k=2
we have
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)

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
bk ’ bk+1 = ’ b (x)dx , (5.13)
and we can rewrite Eq. (5.3) as
n n
aj bj = A(n)b(n) ’ A(x)b (x)dx . (5.14)

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

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)

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
an (k) < n’1 ,
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

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 [63].

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

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)

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

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,
qn’1 < qn (1 ’ n’1/2 )n’1

< qn exp(’ n1/2 /2) ,

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

Thus we obtain
Un = qn (1 + O(exp(’δn1/2 )))

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

<< . .

( 24)

. . >>

Copyright Design by: Sunlight webdesign