Stirling’s approximation is the following (somewhat surprising) approximation of the factorial, , using elementary functions:
( means: the ratio tends to 1 as goes to infinity.) It was proved in 1730 by the Scottish mathematician James Stirling.
This approximation has many applications, among them – estimation of binomial and multinomial coefficients. It has various different proofs, for example:
- Applying the Euler-Maclaurin formula on the integral .
- Using Cauchy’s formula from complex analysis to extract the coefficients of : .
Those proofs are not complicated at all, but they are not too elementary either. In this short note I will present, using guided exercises, 5 different proofs for weaker versions of Stirling’s approximation. In most of the real-life applications, the weaker versions are more than enough. The proofs are self-contained and completely elementary – nothing more than basic calculus (integration and differentiation, Taylor series, definitions of and ) is required.
I am particularly fond of proof no. 2 and the second part of proof no. 4, since I came up with them on my own (although it is highly probable that they were discovered years before, as it happens in the harsh world of Mathematics).
1. First proof: The Rectangle Method
where equality holds only for . Unlike Stirling’s approximation, which is asymptotic in nature, this inequality is true for all – a big advantage.
The basic idea is to compare the sum to the integral .
- Write this inequality logarithmically:
- Show that:
This is the “geometric” step of the proof and the one that gives it its name.
- Prove that .
- By summing the left inequality of 4 over and the right one over , deduce the inequality.
Challenge: This method, of approximating integrals using rectangles, can be refined. Prove the following 2 identities and deduce Stirling’s approximation (except for the constant, though you can find lower and upper bound for it). It is assumed that is a twice differentiable function.
- for some (Midpoint Rule)
- for some (Trapezoid Rule)
2. Second proof: Start at the Conclusion
We’re going to prove that , where is some positive constant. The full approximation states that , and after the proof I challenge you to bound it from above by .
There’s something annoying about the proof – it uses a priori knowledge about . It begins by approximating the ratio , so we had to know Stirling’s approximation beforehand to even think about this ratio.
- (Set-up) Let . We need to prove that converges to some positive finite limit (which will equal ).
- (Warm-up) Verify that and that this ratio converges to 1.
- (Log) As in the previous proof, write everything logarithmically, for simplicity’s sake: . We need to verify that the series converges to a finite limit.
- (Taylor) Use the order-2 Taylor approximation of around to show that (This is the key step!).
- (Conclusion) Prove that converges and deduce that so does . Conclude .
Challenge: Show that increases. Deduce . Given , deduce that Stirling’s Approximation is actually a lower bound: .
3. Third Proof: Monotonic Convergence
This proof gives 2 without integrals or geometrical insights.
- (Induction step) Try to prove the inequality by induction on . Show that the induction step is equivalent to the following inequality:
This inequality is equivalent to 4. (Do you see why?)
- (Limit) Show that both tend to . Thus, it is enough to show that is increasing and is decreasing.
- (Increasing sequence) Show that is monotone increasing by expanding it with Newton’s Binomial Theorem and comparing term by term. (Hint: write the ‘th term as )
- (Decreasing sequence) Do the same with .
4. Fourth Proof: The Power of the Power-Series for
As is analytic and is its own derivative, it has the following well-known power-series expansion around :
We’ll use the fact that the RHS contains factorials to prove , and with some more work we’ll be able to sharpen it to for some . It can actually give the full approximation – and I challenge you to try.
- Plug in the power-series of . Bound from below using the ‘th term: . Deduce . That’s neat – but we can (and will) do better.
- Examine the sequence more carefully and verify the following: is unimodal (it increases and then starts to decrease), and achieves its maximum at (Hint: Consider ). This immediately improves the inequality by a multiplicative constant of 2: .
- We have the equality . Split the series into two sums (each is actually asymptotic to ):
- In 7, consider only the last terms to get the following bound:
Verify that tends to . Deduce that for any less than we have for large enough.
I thank T. Kalvari for a major simplification of this step.
- By doing a more careful analysis, improve the constant. is easy, is harder. Can you get ?
5. Fifth Proof: Central Binomial Coefficient Under Examination
A common usage in combinatorics and probability for Stirling’s Approximation is the estimation of , the central binomial coefficient, as:
We will prove close estimates with almost no analysis.
Credit where credit is due: This proof is mostly based on B. Schmuland’s excellent post on MSE.
- (Baby steps) Prove for .
- (Manipulation) Write as .
- (Analysis) Prove the inequality for . Although it can be proved directly by squaring, there’s also an elegant proof with no computations. Can you find it?
Deduce , with equality only for . (Less elegant analysis shows , which in turn gives .)
- (Monotone Sequence) Use step 2 to deduce that increases, decreases, and so converges to a constant . Moreover, we find the following inequality:
Combining this with Stirling’s approximation, we obtain a new sharp result:
- (Constant) Write as . Together with step 2, show that . Deduce that .
6. Stirling’s Full Approximation
Although it was not the intention of these notes, we can recover Stirling’s Approximation with just a little bit more work. If we combine the 2nd and the 5th proof, we find that . The infinite product is known as Wallis product. I will break down the ad hoc calculation of this product, which gives the final value of . This will give us Stirling’s Approximation.
- Let . Note that is a decreasing sequence that starts with .
- Use integration by parts to show that for , , or: .
- Use the last equality together with the fact that is decreasing to show that .
- Express the limit as an infinite product: . Deduce that .