9.4 TWO ASYMPTOTIC TRICKS 153
3
Now prove th at each of the following three sums is small: L(n)
=
x
ok(n);
tb(n)
=
x
xc (n)
‘Jk(n)
;
kET,
MT, =
x
(ck(n)l.
(9W
If all three steps can be completed successfully, we have a good estimate: t
ak(n)
=
t
kED,uT,
bk(n)
+
o(L(n))
+ O(xb(n))
+ o(L(n))
.
kED,uT,
Here’s why. We can “chop off” the tail of the given sum, getting a good estimate in the range D, where a good estimate is necessary: x
ak(n) =
x @k(n)
G-D,
+ O(ck(n)))
kCD,
=
t
bk(n)
+ o&(n)).
ND,
And we can replace the tail with another one, even though the new tail might be a terrible approximation to the old, because the tails don’t really matter: x
Asymptotics is the art of knowing where to be sloppy and where to be precise.
ak(n) =
x
&T,
@k(n)
- bk(n)
+ ak(n))
MT, =
x h(n)
+
O(xb(n))
+
o&,(n)).
MT, When we evaluated the sum in (g.6o), for example, we had ak(n)
=
[06k
h(n)
=
Sk/n,
ck(n)
=
kgk/n(n-k);
the ranges of summation were
T,, = {n,n+l,...};
D, = {O,l,..., n - l } , and we found that
x,(n)
= 0, Lb(n)
= o((logn)2/n2),
xc(n) = o((logn)3/n2).
This led to (9.61). Similarly, when we estimated 0(n) in (9.55) we had ak(n) =
v(k)
[n/k]
D, = {1,2 ,..., n},
Ll+n/k]
,
bk(n)
=
dk)n2/k2
,
ck(n) =
n/k;
T,, = {n+l,n+2,...}.
We derived (9.56) by observing that E,(n) = 0, xb(n) = O(n), and L,(n) = O(nlogn).