[The "significant inaccuracy" is dramatically reduced by using the correct formula]

### n! ~ (2πn)^{1/2}n^{n}e^{-n}

Stirling's

formula provides an

approximation to the

factorial function. The approximation is

asymptotically correct for large n (written ~) which means that the ratio of n! and the approximation tends to 1 as n goes to

infinity. Still, the approximation is quite

accurate even for small values of n (we have two correct

significant figures for n ≥ 7).

Stirling's formula is good for making estimates in combinatorics, and since combinatorial problems appear naturally in most branches of mathematics (particularly in probability theory) this makes Stirling's formula very useful.

**Simple example:**

The number of ways to partition a set with 3n members into three sets of size n is

(3n)!(n!)^{-3} ~ 3^{3n+1/2}/2πn

In order to use the formula we should of course convince ourselves that it is correct.

As an informal justification for why there should be some formula like Stirling's we can begin by considering approximations to ln(n!). By comparing the sum ln(1) + ... + ln(n) with the integral ∫_{0}^{n}ln(x)dx it is obvious that ln(n!) ~ n ln(n). This is the weak form of Stirling's formula. In order to derive the strong form we have to work a bit harder.

**Proposition:**

n! ~ (2πn)^{1/2}n^{n}e^{-n}

**Proof:**

The proof consists of two parts (and a lot of dull equations). First we show that n! ~ Cn^{n+1/2}e^{-n} for some constant C, and then that the value of the constant is C = (2π)^{1/2}.

We know that for all positive x

1 - x + x^{2} - x^{3} < 1/(1+x) < 1 - x + x^{2}

Integrating this gives the inequality

x - x^{2}/2 + x^{3}/3 - x^{4}/4 < ln(1+x) < x - x^{2}/2 + x^{3}/3

Now let h_{n} = ln(n!e^{n}n^{-n-1/2}). Then

h_{n} - h_{n+1} = ln(n!e^{n}(n+1)^{n+3/2}/(n+1)!e^{n+1}n^{n+1/2}) = ln((n + 1/n)^{n+1/2}/e) = (n+1/2)ln(1 + 1/n) - 1

Using the estimation for ln(1+ 1/n) we obtain after some algebra

n^{-2}/12 - n^{-3}/12 - n^{-4}/8 < h_{n} - h_{n+1} < n^{-2}/12 + n^{-3}/6

For n ≥ 2 we see that h_{n} - h_{n+1} is positive, so the sequence h_{n} is a decreasing. Using the other inequality we can find a lower bound for the sequence by summing the series n^{-2}/12 + n^{-3}/6, which converges. By the completeness of the reals this implies that h_{n} tends to some finite limit A as n → ∞. Thus

n! ~ e^{A}n^{n+1/2}e^{-n}

In order to complete the proof we need to pin down the value of A. An (admittedly somewhat unintuitive) way of doing this is to consider the sequence of integrals

I_{n} = ∫_{0}^{π/2}sin^{n}θ dθ

I_{0} = π/2, I_{1} = 1 by direct integration, and integration by parts gives the recursion relation I_{n} = (n-1)I_{n-2}/n for n ≥ 2. Hence we obtain different expressions for I_{n} depending on whether n is even or odd:

I_{2n} = (2^{n}n!)^{-2}(2n)!π/2

I_{2n+1} = (2^{n}n!)^{2}/(2n+1)!

Using our proto-version n! ~ e^{A}n^{n+1/2}e^{-n} of Stirling's formula we can write (after a lot of cancellations)

I_{2n}/I_{2n+1} = (2n+1)((2n)!)^{2}(2^{n}n!)^{-4}π/2 ~ (2n+1)(2/n)e^{-2A}π/2 → 2πe^{-2A}

But we also know that I_{n} is a decreasing sequence, so

1 < I_{2n}/I_{2n+1} < I_{2n-1}/I_{2n+1} = 1 +(2n)^{-1} → 1

as n → ∞. Since limits are unique

2πe^{-2A} = 1

e^{A} = (2π)^{1/2}

n! ~ (2πn)^{1/2}n^{n}e^{-n}