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! ∼

√

2π

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 suﬃcient 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| ∞.