Today I wanted to discuss something I learnt last week in my Probability course: Stirling’s Formula. Stirling’s Formula is an approximation for factorials, and leads to quite accurate results even for small values of *n*.

The formula can be written in two ways:

or

where the ~ sign means that the two quantities are asymptotic (i.e. their ratios tend to 1 as *n* tends to infinity).

## Proof of Stirling’s Formula

The following identity arises using integration by parts:

Taking *f(x) = log x*, we obtain

Next, sum over *n*, and by recalling that **log x + log y = log xy** we get the following expression:

where

Next, define

which allows us to rearrange the above expression to:

So as *n* tends to infinity we get

**How do we show that ?**

Firstly, note that from (*) it follows that

So, we need to show that

Let’s set

Note that I0=π/2 and I1 = 1. Then for n≥2, we can integrate by parts to see that

And so, we obtain the following two expressions:

In is decreasing in *n* and In/In-2 → 1, so it follows that I2n/I2n+1 → 1. Therefore,

as required.

Although the end result is satisfying, I find that some steps in this proof are like ‘pulling-a-rabbit-out-of-a-hat’! What do you think? Mx

Asymptotic Analysis

LikeLike