In mathematics, Stirling's approximation (or Stirling's formula) is an asymptotic approximation for factorials. It is named after James Stirling, though a related but less precise result was first stated by Abraham de Moivre.

One way of stating the approximation involves the logarithm where the big O notation. In computer science applications such as the worst-case lower bound for comparison sorting, it is convenient to instead use the binary logarithm tends to infinity.

History

The formula was first discovered by Abraham de Moivre

.

Derivation

with an integral

, one considers its natural logarithm, as this is a slowly varying function

is the approximation by the trapezoid rule

and the error in this approximation is given by the Euler–Maclaurin formula

is a Bernoulli number, and

. Because the remainder

where big-O notation

. For

tends to infinity and using Wallis' product. Therefore, one obtains Stirling's formula.

Alternative derivations

using the gamma function (as can be seen by repeated integration by parts). Rewriting and changing variables Applying Laplace's method

Higher orders

, which can be obtained programmatically.

Complex-analytic version

A complex-analysis version of this method as a Taylor coefficient computed by Cauchy's integral formula

This line integral can then be approximated using the saddle-point method. The dominant portion of the integral near the saddle point is then approximated by a real integral and Laplace's method, while the remaining portion of the integral can be bounded above to give an error term.

Using the Central Limit Theorem and the Poisson distribution

An alternative version uses the fact that the Poisson distribution converges to a normal distribution by the Central Limit Theorem.

, their density functions will be approximately the same:

Evaluating this expression at the mean, at which the approximation is particularly accurate, simplifies this expression to:

Taking logs then results in

which can easily be rearranged to give:

gives the usual, more precise form of Stirling's approximation.

Speed of convergence and error estimates

Stirling's formula is in fact the first approximation to the following series (now called the Stirling series):

An explicit formula for the coefficients in this series was given by G. Nemes. Further terms are listed in the On-Line Encyclopedia of Integer Sequences as and . The first graph in this section shows the relative error, for 1 through all 5 terms listed above. The coefficients have the following asymptotic formula:which shows that it grows superexponentially, and that by the ratio test the radius of convergence is zero.

However, the representation obtained directly from the Euler–Maclaurin approximation, in which the correction term itself is the argument of the exponential function, converges much faster (needs half the number of correction terms for the same accuracy):

As , the error in the truncated series is asymptotically equal to the first omitted term. This is an example of an asymptotic expansion. It is not a convergent series; for any particular there are only so many terms of the series that improve accuracy, after which accuracy worsens. This is shown in the next graph, which shows the relative error versus the number of terms in the series, for larger numbers of terms. More precisely, let terms evaluated at which, when small, is essentially the relative error.

it is known that the error in truncating the series is always of the opposite sign and at most the same magnitude as the first omitted term.

Other bounds, due to Robbins,

Stirling's formula for the gamma function

where denotes the gamma function.

However, the gamma function, unlike the factorial, is more broadly defined for all complex numbers other than non-positive integers; nevertheless, Stirling's formula may still be applied. If

is the th Bernoulli number is not convergent, so this formula is just an asymptotic expansion large enough in absolute value, when , where is positive, with an error term of

is replaced with .

A further application of this asymptotic expansion is for complex argument with constant . See for example the Stirling formula applied in of the Riemann–Siegel theta function on the straight line .

A convergent version of Stirling's formula

Thomas Bayes showed, in a letter to John Canton published by the Royal Society in 1763, that Stirling's formula did not give a convergent series. Obtaining a convergent version of Stirling's formula entails evaluating Binet's formula

One way to do this is by means of a convergent series of inverted rising factorials where denotes the Stirling numbers of the first kind which converges when . Stirling's formula may also be given in convergent form as

Versions suitable for calculators

can be obtained by rearranging Stirling's extended formula and observing a coincidence between the resultant power series and the Taylor series expansion of the hyperbolic sine function. This approximation is good to more than 8 decimal digits for with a real part greater than 8. Robert H. Windschitl suggested it in 2002 for computing the gamma function with fair accuracy on calculators with limited program or register memory.

Gergő Nemes proposed in 2007 an approximation which gives the same number of exact digits as the Windschitl approximation but is much simpler:

An alternative approximation for the gamma function stated by Srinivasa Ramanujan in Ramanujan's lost notebook for . The equivalent approximation for has an asymptotic error of

The approximation may be made precise by giving paired upper and lower bounds; one such inequality is

Equation for discrete cases

For discrete cases, rather than the asymptotic formula described above, a more accurate equation, and much easier to prove result has been derived by T. S. Nanjundiah:

or further, we can deduce that:

To prove this, we first assume that:

It is easy to calculate that:

and, by combining the Taylor's series of logarithms:

subtracting them,

let the two variables be equal,

replacing with , we get:

we have that:

To calculate the sum, we force them to be a geometric series:

,

, thus we have that

according to monotone convergence theorem

combined with Wallis Formula, which finalize our proof of the asymptotic case.

And notice that for every , rewrite the formula by substituting , we get:

, we have:

Here, we can derive that:

, finally we prove that:

See also

• Lanczos approximation

• Spouge's approximation

References

Further reading

External links

• Peter Luschny,