Mathematics for Computer Science

13.5. Products 523

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 


.n1/
n/

Dln.1/Cln.2/Cln.3/C


Cln.n1/Cln.n/

D

Xn

iD 1

ln.i/:

Unfortunately, no closed form for this sum is known. However, we can apply
Theorem 13.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 13.3.2, this means that

nln.n/nC 1 

Xn

iD 1

ln.i/ nln.n/nC 1 Cln.n/:

Exponentiating then gives

nn

en^1

 nŠ 

nnC^1

en^1

: (13.23)

This means thatnŠis within a factor ofnofnn=en^1.

13.5.1 Stirling’s Formula

The most commonly used product in discrete mathematics is probablynŠ, and
mathematicians have workedto find tight closed-form bounds on its value. The
most useful bounds are given in Theorem 13.5.1.

Theorem 13.5.1(Stirling’s Formula).For alln 1 ,

nŠD

p

2n

n

e

n

e.n/

where
1
12nC 1
.n/

1

12n

: