Chapter 14 Sums and Asymptotics428
Approximation n1 n10 n100 n 1000
p
2n
n
e
n
<10% <1% <0.1% <0.01%
p
2n
n
e
n
e1=12n <1% <0.01% <0.0001% <0.000001%
Table 14.1 Error bounds on common approximations for nŠ from Theo-
rem 14.5.1. For example, ifn 100 , then
p
2n
n
e
n
approximatesnŠ to
within 0.1%.
of the correct value. Forn 10 , this means we will be within 1% of the correct
value. Forn 100 , the error will be less than 0.1%.
If we need an even closer approximation fornŠ, then we could use either
p
2n
n
e
n
e1=12n
or p
2n
n
e
n
e1=.12nC1/
depending on whether we want an upper bound or a lower bound, respectively. By
Theorem 14.5.1, we know that both bounds will be within a factor of
e
12n^1 12n^1 C 1
De
1
144n^2 C12n
of the correct value. Forn 10 , this means that either bound will be within 0.01%
of the correct value. Forn 100 , the error will be less than 0.0001%.
For quick future reference, these facts are summarized in Corollary 14.5.2 and
Table 14.1.
Corollary 14.5.2.
nŠ <
p
2n
n
e
n
8
ˆ<
ˆ:
1:09 forn1;
1:009 forn10;
1:0009 forn100:
14.6 Double Trouble
Sometimes we have to evaluate sums of sums, otherwise known asdouble summa-
tions. This sounds hairy, and sometimes it is. But usually, it is straightforward—
you just evaluate the inner sum, replace it with a closed form, and then evaluate the
