Stirling's approximation

Stirling's approximation (or Stirling's formula) is an approximation for large factorials. It is named in honour of James Stirling. Formally, it states:

<math>\lim_{n \rightarrow \infty} {n!\over \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n} } = 1</math>

which is often written as

<math>n! \sim \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}</math>

(See limit, square root, π, e.) For large n, the right hand side is a good approximation for n!, and much faster and easier to calculate. For example, the formula gives for 30! the approximation 2.6451 × 10³² while the correct value is about 2.6525 × 10³².

Table of contents 1 Consequences 2 Speed of convergence and error estimates 3 Derivation 4 History

Consequences

It can be shown that

<math>n^n \ge n! \ge \left(\frac{n}{2}\right)^\frac{n}{2}</math>

using Stirling's appoximation.

Speed of convergence and error estimates

The speed of convergence of the above limit is expressed by the formula

<math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}\left(1 + \Theta\left(\frac{1}{n}\right)\right)</math>

where Θ(1/n) denotes a function whose asymptotical behavior for n→∞ is like a constant times 1/n; see Big O notation.

More precisely still:

<math>n! = \sqrt{2 \pi n} \; \left(\frac{n}{e}\right)^{n}e^{\lambda_n}</math>

with

<math>\frac{1}{12n+1} < \lambda_n < \frac{1}{12n}</math>

Derivation

The formula, together with precise estimates of its error, can be derived as follows. Instead of approximating n!, one considers the natural logarithm ln(n!) = ln(1) + ln(2) + ... + ln(n); the Euler-Maclaurin formula gives estimates for sums like these. The goal, then, is to show the approximation formula in its logarithmic form:

<math>\ln n! \approx \left(n+\frac{1}{2}\right)\ln n - n +\ln\left(\sqrt{2\pi}\right)</math>

History

The formula was first discovered by Abraham de Moivre in the form

<math>n!\sim [{\rm constant}]\cdot n^{n+1/2} e^{-n}</math>

Stirling's contribution consisted of showing that the "constant" is <math>\sqrt{2\pi}</math>.