[The "significant inaccuracy" is dramatically reduced by using the correct formula]
n! ~ (2πn)1/2nne-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 ~ 33n+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 ∫0nln(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/2nne-n
Proof:
The proof consists of two parts (and a lot of dull equations). First we show that n! ~ Cnn+1/2e-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 + x2 - x3 < 1/(1+x) < 1 - x + x2
Integrating this gives the inequality
x - x2/2 + x3/3 - x4/4 < ln(1+x) < x - x2/2 + x3/3
Now let hn = ln(n!enn-n-1/2). Then
hn - hn+1 = ln(n!en(n+1)n+3/2/(n+1)!en+1nn+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 < hn - hn+1 < n-2/12 + n-3/6
For n ≥ 2 we see that hn - hn+1 is positive, so the sequence hn 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 hn tends to some finite limit A as n → ∞. Thus
n! ~ eAnn+1/2e-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
In = ∫0π/2sinnθ dθ
I0 = π/2, I1 = 1 by direct integration, and integration by parts gives the recursion relation In = (n-1)In-2/n for n ≥ 2. Hence we obtain different expressions for In depending on whether n is even or odd:
I2n = (2nn!)-2(2n)!π/2
I2n+1 = (2nn!)2/(2n+1)!
Using our proto-version n! ~ eAnn+1/2e-n of Stirling's formula we can write (after a lot of cancellations)
I2n/I2n+1 = (2n+1)((2n)!)2(2nn!)-4π/2 ~ (2n+1)(2/n)e-2Aπ/2 → 2πe-2A
But we also know that In is a decreasing sequence, so
1 < I2n/I2n+1 < I2n-1/I2n+1 = 1 +(2n)-1 → 1
as n → ∞. Since limits are unique
2πe-2A = 1
eA = (2π)1/2
n! ~ (2πn)1/2nne-n