1.1. Simple random walk 5
the expression on the right-hand side leads to studying the behavior
of n! as n gets large. This is the goal of the next section.
1.1.2. Stirling’s formula. Stirling’s formula states that as n ∞,
n!


nn+
1
2
e−n,
where means that the ratio of the two sides tends to 1. We will
prove this in the next two subsections. In this subsection we will
prove that there is a positive number C0 such that
(1.1) lim
n→∞
bn = C0, where bn =
n!
nn+
1
2
e−n
,
and in Section 1.1.3 we show that C0 =

2π.

Suppose an is a sequence of positive numbers going to infinity and
we want to find a positive function f(n) such that an/f(n) converges to a
positive constant L. Let bn = an/f(n). Then
bn = b1
n
j=2
bj
bj−1
= b1
n
j=2
[1 + δj ],
where
δj =
bj
bj−1
1,
and
lim
n→∞
log bn = log b1 + lim
n→∞
n
j=2
log[1 + δj ] = log b1 +

j=2
log[1 + δj ],
provided that the sum converges. A necessary condition for convergence is that
δn 0. The Taylor’s series for the logarithm shows that | log[1 + δn]| c |δn|
for |δn| 1/2, and hence a sufficient condition for uniform convergence of the
sum is that

n=2
|δn| ∞.
Although this argument proves that the limit exists, it does not determine the
value of the limit.
To start, it is easy to check that b1 = e and if n 2, then
(1.2)
bn
bn−1
= e
n 1
n
n−
1
2
= e 1
1
n
n
1
1
n
−1/2
.
Let δn = (bn/bn−1) 1. We will show that

|δn| ∞.
Previous Page Next Page