5 Short Proofs of Simplified Stirling’s Approximation

(This post was converted from tex to html using the wonderful free tool “LaTeX  to WordPress”. You can find a PDF version in the “Documents” section.)

0. Introduction

Stirling’s approximation is the following (somewhat surprising) approximation of the factorial, { n!}, using elementary functions:

\displaystyle  n!\sim(\frac{n}{e})^{n}\sqrt{2\pi n} \ \ \ \ \ (1)

({f(n)\sim g(n)} means: the ratio {\frac{f(n)}{g(n)}} tends to 1 as {n} 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 {\int_{1}^{n} \ln x \, dx}.
  • Using Cauchy’s formula from complex analysis to extract the coefficients of {e^{x}}: {\frac{1}{n!}=\frac{1}{2\pi i}\int_{|z|=n}\frac{e^{z}}{z^{n+1}} \, dz}.

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 {e} and {e^{x}}) 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).

Let’s begin!

1. First proof: The Rectangle Method

We’ll prove the following double inequality:

\displaystyle   e(\frac{n}{e})^{n}\le n!\le en(\frac{n}{e})^{n} \ \ \ \ \ (2)

where equality holds only for {n=1}. Unlike Stirling’s approximation, which is asymptotic in nature, this inequality is true for all {n \ge 1} – a big advantage.

The basic idea is to compare the sum {\sum \ln i} to the integral {\int\ln x \, dx}.

  1. Write this inequality logarithmically:

    \displaystyle  n\ln n-n+1\le\sum_{i=1}^{n}\ln i\le n\ln n-n+1+\ln n \ \ \ \ \ (3)

  2. Show that:

    \displaystyle  \int_{i-1}^{i}\ln xdx<\ln i<\int_{i}^{i+1}\ln x \, dx \ \ \ \ \ (4)

    This is the “geometric” step of the proof and the one that gives it its name.

  3. Prove that {\int\ln x \, dx=x\ln x-x+C}.

  4. By summing the left inequality of 4 over {i=2,\cdots,n} and the right one over {i=1,\cdots,n-1}, 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 {f} is a twice differentiable function.

  • {\int_{t-\frac{1}{2}}^{t+\frac{1}{2}} f(x) \, dx = f(t) + \frac{f''( \xi )}{24}} for some {\xi \in [ t-\frac{1}{2},t+\frac{1}{2} ]} (Midpoint Rule)
  • {\int_{t}^{t+1} f(x) \, dx = \frac{f(t)+f(t+1)}{2} - \frac{f''(\xi)}{12}} for some {\xi \in [t, t+1 ]} (Trapezoid Rule)

2. Second proof: Start at the Conclusion

We’re going to prove that {n!\sim C(\frac{n}{e})^{n}\sqrt{n}}, where {C} is some positive constant. The full approximation states that {C=\sqrt{2\pi} \approx 2.5066}, and after the proof I challenge you to bound it from above by {e \approx 2.71828}.
There’s something annoying about the proof – it uses a priori knowledge about {n!}. It begins by approximating the ratio {\frac{(\frac{n}{e})^{n}\sqrt{n}}{n!}}, so we had to know Stirling’s approximation beforehand to even think about this ratio.

  1. (Set-up) Let {a_{n}=\frac{(\frac{n}{e})^{n}\sqrt{n}}{n!}}. We need to prove that {a_{n}} converges to some positive finite limit (which will equal {C^{-1}}).
  2. (Warm-up) Verify that {\frac{a_{n+1}}{a_{n}}=\frac{(1+\frac{1}{n})^{n+\frac{1}{2}}}{e}} and that this ratio converges to 1.
  3. (Log) As in the previous proof, write everything logarithmically, for simplicity’s sake: {\ln(a_{n})=\sum_{i=1}^{n-1}\ln(\frac{a_{i+1}}{a_{i}})+\ln(a_{1})}. We need to verify that the series {\sum_{i=1}^{\infty}\ln(\frac{a_{i+1}}{a_{i}})} converges to a finite limit.
  4. (Taylor) Use the order-2 Taylor approximation of {\ln(1+x)} around {x=0} to show that {\ln(\frac{a_{i+1}}{a_{i}})=O(i^{-2})} (This is the key step!).
  5. (Conclusion) Prove that {\sum_{i\ge1}i^{-2}} converges and deduce that so does {\sum_{i\ge1}\ln(\frac{a_{i+1}}{a_{i}})}. Conclude {n!\sim C(\frac{n}{e})^{n}\sqrt{n}}.

Challenge: Show that {\{ a_n \}_{n\ge 1}} increases. Deduce {n! \le e(\frac{n}{e})^{n}\sqrt{n}}. Given {C=\sqrt{2 \pi}}, deduce that Stirling’s Approximation is actually a lower bound: {n! \ge (\frac{n}{e})^{n} \sqrt{2 \pi n}}.

3. Third Proof: Monotonic Convergence

This proof gives 2 without integrals or geometrical insights.

  1. (Induction step) Try to prove the inequality by induction on {n}. Show that the induction step is equivalent to the following inequality:

    \displaystyle  (1+\frac{1}{n})^{n}<e<(1+\frac{1}{n})^{n+1} \ \ \ \ \ (5)

    This inequality is equivalent to 4. (Do you see why?)

  2. (Limit) Show that both {(1+\frac{1}{n})^{n},(1+\frac{1}{n})^{n+1}} tend to {e}. Thus, it is enough to show that {(1+\frac{1}{n})^{n}} is increasing and {(1+\frac{1}{n})^{n+1}} is decreasing.
  3. (Increasing sequence) Show that {a_{n}=(1+\frac{1}{n})^{n}} is monotone increasing by expanding it with Newton’s Binomial Theorem and comparing {a_{n},a_{n+1}} term by term. (Hint: write the {k}‘th term as {\frac{1}{k!}\prod_{0\le i<k}(1-\frac{i}{n})})
  4. (Decreasing sequence) Do the same with {b_{n}=(1+\frac{1}{n})^{n+1}}.

4. Fourth Proof: The Power of the Power-Series for {e^{x}}

As {e^{x}} is analytic and is its own derivative, it has the following well-known power-series expansion around {0}:

\displaystyle  e^x =\sum_{k=0}^{\infty} \frac{x^{k}}{k!} \ \ \ \ \ (6)

We’ll use the fact that the RHS contains factorials to prove {n!>(\frac{n}{e})^{n}}, and with some more work we’ll be able to sharpen it to { n!>C\sqrt{n}(\frac{n}{e})^{n}} for some {C>0}. It can actually give the full approximation – and I challenge you to try.

  1. Plug {x=n} in the power-series of {e^{x}}. Bound {e^{n}} from below using the {n}‘th term: {e^{n}>\frac{n^{n}}{n!}}. Deduce {n!>(\frac{n}{e})^{n}}. That’s neat – but we can (and will) do better.
  2. Examine the sequence {\{a_{k}=\frac{n^{k}}{k!}\}_{k\ge 0}} more carefully and verify the following: {a_k} is unimodal (it increases and then starts to decrease), and achieves its maximum at {k=n-1,n} (Hint: Consider {\frac{a_{k+1}}{a_k}}). This immediately improves the inequality by a multiplicative constant of 2: {n!>2(\frac{n}{e})^{n}}.
  3. We have the equality {n! = (\frac{n}{e})^{n} \sum_{k=0}^{\infty}\frac{n!}{k!}n^{k-n}}. Split the series into two sums (each is actually asymptotic to {\frac{1}{2} \sqrt{2 \pi n}}):

    \displaystyle   \sum_{k=0}^{n-1}\frac{n!}{k!}n^{k-n} = \sum_{k=0}^{n-1} \prod_{i=0}^{n-k-1}(1-\frac{i}{n}) \ \ \ \ \ (7)

    \displaystyle   \sum_{k=n}^{\infty}\frac{n!}{k!}n^{k-n} = \sum_{k=n}^{\infty} \prod_{i=0}^{k-n}(1+\frac{i}{n})^{-1} \ \ \ \ \ (8)

  4. In 7, consider only the last {\lfloor \sqrt{n} \lfloor} terms to get the following bound:

    \displaystyle  n!>(\frac{n}{e})^{n}\lfloor \sqrt{n} \rfloor\prod_{i=0}^{\lfloor \sqrt{n} \rfloor}(1-\frac{i}{n})\ge(\frac{n}{e})^{n}\lfloor \sqrt{n} \rfloor (1-\frac{\lfloor \sqrt{n} \rfloor}{n})^{\lfloor \sqrt{n} \rfloor} \ \ \ \ \ (9)

    Verify that {(1-\frac{\lfloor \sqrt{n} \rfloor}{n})^{\lfloor \sqrt{n} \rfloor}} tends to {\frac{1}{e}}. Deduce that for any {C} less than {\frac{1}{e}} we have {n! > (\frac{n}{e})^{n}\sqrt{n}C} for {n} large enough.
    I thank T. Kalvari for a major simplification of this step.

  5. By doing a more careful analysis, improve the constant. {\frac{1}{\sqrt{2e}}} is easy, {\frac{1}{\sqrt{e}}} is harder. Can you get {\sqrt{\frac{\pi}{2}}}?

Challenge: Show that both 7,8 are asymptotic to {\int_{0}^{\infty} e^{-\frac{x^2}{2n}} \, dx = \sqrt{n \frac{\pi}{2}}}. (Hint: {e^{\frac{x}{1+x}} \le 1+x \le e^{x}} for {x \ge 0})

5. Fifth Proof: Central Binomial Coefficient Under Examination

A common usage in combinatorics and probability for Stirling’s Approximation is the estimation of {\binom{2n}{n}}, the central binomial coefficient, as:

\displaystyle  \frac{(2n)!}{n!^2} \sim \frac{(\frac{2n}{e})^{2n}\sqrt{4n\pi}}{((\frac{n}{e})^{n}\sqrt{2\pi n})^{2}} = \frac{4^{n}}{\sqrt{n\pi}} \ \ \ \ \ (10)

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.

  1. (Baby steps) Prove {4^n > \binom{2n}{n} > \frac{4^{n}}{2n+1}} for {n \ge 1}.
  2. (Manipulation) Write {\binom{2n}{n}4^{-n}} as {\prod_{i=1}^{n}(1-\frac{1}{2i})}.
  3. (Analysis) Prove the inequality {\sqrt{\frac{i-1}{i}} < 1-\frac{1}{2i} < \sqrt{\frac{i}{i+1}}} for {i\ge2}. Although it can be proved directly by squaring, there’s also an elegant proof with no computations. Can you find it?

    Deduce {\frac{4^{n}}{\sqrt{n+1}}\ge\binom{2n}{n}\ge\frac{4^{n}}{\sqrt{4n}}}, with equality only for {n=1}. (Less elegant analysis shows {1-\frac{1}{2i}\le\sqrt{\frac{3(i-1)+1}{3i+1}}}, which in turn gives {\frac{4^{n}}{\sqrt{3n+1}}\ge\binom{2n}{n}}.)

  4. (Monotone Sequence) Use step 2 to deduce that {2n(\binom{2n}{n}4^{-n})^{2}} increases, {(2n+1)(\binom{2n}{n}4^{-n})^{2}} decreases, and so {\binom{2n}{n}\frac{\sqrt{2n}}{4^{n}}} converges to a constant {C}. Moreover, we find the following inequality:

    \displaystyle  \frac {4^n}{\sqrt{n+\frac{1}{2}}} \sqrt{\frac{C}{2}} \le \binom{2n}{n} \le \frac{4^n}{\sqrt{n}}\sqrt{\frac{C}{2}} \ \ \ \ \ (11)

    Combining this with Stirling’s approximation, we obtain a new sharp result:

    \displaystyle  \frac {4^n}{\sqrt{\pi (n+\frac{1}{2})}} \le \binom{2n}{n} \le \frac{4^n}{\sqrt{\pi n}} \ \ \ \ \ (12)

  5. (Constant) Write {\binom{2n}{n}4^{-n}} as {\frac{1}{2n}\prod_{j=1}^{n-1}(1+\frac{1}{2j})}. Together with step 2, show that {(\binom{2n}{n}4^{-n})^{2}=\frac{1}{2n}\prod_{j=1}^{n-1}(1+\frac{1}{2j})\prod_{j=1}^{n}(1-\frac{1}{2j})}. Deduce that {C=\prod_{j \ge 1}(1-\frac{1}{2j})(1+\frac{1}{2j})}.

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 {n! \sim 2\sqrt{\prod_{j \ge 1}(\frac{2j}{2j-1}\frac{2j}{2j+1})}\sqrt{n}(\frac{n}{e})^n}. 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 {\frac{\pi}{2}}. This will give us Stirling’s Approximation.

  1. Let {I_n = \int_{0}^{\pi} \sin^{n} (x) \, dx}. Note that {I_n} is a decreasing sequence that starts with {I_0 = \pi, I_1 = 2}.
  2. Use integration by parts to show that for {n\ge 2}, {I_n = (n-1)(I_{n-2} - I_{n})}, or: {\frac{I_n}{I_{n-2}} = \frac{n-1}{n}}.
  3. Use the last equality together with the fact that {I_n} is decreasing to show that {\lim_{n \rightarrow \infty} \frac{I_{2n}}{I_{2n+1}}=1}.
  4. Express the limit as an infinite product: {\frac{I_0}{I_1} \prod_{j \ge 1} \frac{2j-1}{2j} \frac{2j+1}{2j}}. Deduce that {\prod_{j \ge 1}(\frac{2j}{2j-1}\frac{2j}{2j+1}) = \frac{\pi}{2}}.
Advertisements

About Ofir Gorodetsky

Graduate student at TAU. Can be contacted at bambaman1 at gmail dot com.
This entry was posted in analysis, Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s