Chapter 14 Sums and Asymptotics426
14.5 Products
We’ve covered several techniques for finding closed forms for sums but no methods
for dealing with products. Fortunately, we do not need to develop an entirely new
set of tools when we encounter a product such as
nŠWWD
Yn
iD 1
i: (14.27)
That’s because we can convert any product into a sum by taking a logarithm. For
example, if
PD
Yn
iD 1
f.i/;
then
ln.P/D
Xn
iD 1
ln.f.i//:
We can then apply our summing tools to find a closed form (or approximate closed
form) for ln.P/and then exponentiate at the end to undo the logarithm.
For example, let’s see how this works for the factorial functionnŠWe start by
taking the logarithm:
ln.nŠ/Dln.1 2 3 .n 1/n/
Dln.1/Cln.2/Cln.3/CCln.n 1/Cln.n/
D
Xn
iD 1
ln.i/:
Unfortunately, no closed form for this sum is known. However, we can apply
Theorem 14.3.2 to find good closed-form bounds on the sum. To do this, we first
compute
Zn
1
ln.x/dxDxln.x/ x
ˇ
ˇˇn
1
Dnln.n/ nC1:
Plugging into Theorem 14.3.2, this means that
nln.n/ nC 1
Xn
iD 1
ln.i/ nln.n/ nC 1 Cln.n/:
