Stirling's approximation

From Academic Kids

In mathematics, 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.6452 × 1032 while the correct value is about 2.6525 × 1032. The error is less than 0.3% in this case.

Contents

Derivation

The formula, together with precise estimates of its error, can be derived as follows. Instead of approximating n!, one considers the natural logarithm

<math>\ln n! = \ln 1 + \ln 2 + \ldots + \ln n <math>

Then, we can apply Euler-Maclaurin formula by putting f(x) = ln(x) to find an approximation of the value of ln(n!).

<math>\ln (n-1)! = n \ln n - n + 1 - \frac{\ln n}{2} + \sum_{k=2}^{m} \frac{B_k {(-1)}^k}{k(k-1)} ( \frac{1}{n^{k-1}} - 1 ) + R <math>

where Bk is Bernoulli number and R is the remainder of Euler-Maclaurin formula.

Then, we can then take limit on both sides,

<math>\lim_{n \to \infty} ( \ln n! - n \ln n + n - \frac{\ln n}{2} ) = 1 + \sum_{k=2}^{m} \frac{B_k {(-1)}^k}{k(k-1)} + \lim_{n \to \infty} R<math>

Let the above limit be y and compound the above two formula, we get the approximation formula in its logarithmic form:

<math>\ln n! = (n+\frac{1}{2}) \ln n - n + y + \sum_{k=2}^{m} \frac{B_k {(-1)}^k}{k(k-1)n^{k-1}} + O(\frac{1}{n^m})<math>

where O(f(n)) is Big-O notation.

Just take the exponential on both sides, and choose any positive integer m, say 1. We get the formula with an unknown term ey.

<math>n! = e^y \sqrt{n}~{( \frac{n}{e} )}^n ( 1 + O(\frac{1}{n}) )<math>

The unknown term ey can be found by taking the limit on both sides as n tends to infinity and using Wallis' product. One can estimate the value of ey is <math>\sqrt{2 \pi}<math>. Therefore, we get Stirling's formula:

<math>n! = \sqrt{2 \pi n}~{( \frac{n}{e} )}^n ( 1 + O(\frac{1}{n}) )<math>

The formula may also be obtained by repeated integration by parts. The leading term can be found through the method of steepest descent.

Speed of convergence and error estimates

More precisely,

<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>

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

<math>
 n!=\sqrt{2\pi n}\left({n\over e}\right)^n
 \left(
  1
  +{1\over12n}
  +{1\over288n^2}
  -{139\over51840n^3}
  -{571\over2488320n^4}
  + \cdots
 \right)
<math>

As <math>n \to \infty<math>, the error in the truncated series is asymptotically equal to the first omitted term. This is an example of an asymptotic expansion.

The asymptotic expansion of the logarithm is also called Stirling's series:

<math>
 \ln n!=n\ln n - n + {1\over 2}\ln(2\pi n)
  +{1\over12n}
  -{1\over360n^3}
  +{1\over1260n^5}
  -{1\over 1680n^7}
  +\cdots
<math>

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

Stirling's formula for the Gamma function

Stirling's formula may also be applied to the Gamma function

<math>\Gamma(z+1) = \Pi(z) = z!<math>

defined for all complex numbers other than non-positive integers. If <math>\Re(z) > 0<math> then

<math>\ln \Gamma (z) = (z-\frac12)\ln z -z + \frac{\ln {2 \pi}}{2} + 2 \int_0^\infty \frac{\arctan \frac{t}{z}}{\exp(2 \pi t)-1} dt<math>

Repeated integration by parts gives the asymptotic expansion

<math>\ln \Gamma (z) = (z-\frac12)\ln z -z + \frac{\ln {2 \pi}}{2} + \sum_{n=1}^\infty \frac{B_{2n}}{2n(2n-1)z^{2n-1}}<math>

where Bn is the nth Bernoulli number. The formula is valid for z large enough in absolute value when <math>|\arg z| < \pi - \epsilon<math>, where ε is positive, with an error term of <math>O(z^{-m - 1/2})<math> when the first m terms are used.

A convergent version of Stirling's formula

Obtaining a convergent version of Stirling's formula entails evaluating

<math>\int_0^\infty \frac{2\arctan \frac{t}{z}}{\exp(2 \pi t)-1}\, dt

= \ln\Gamma (z) - (z-\frac12)\ln z +z - \frac12\ln(2\pi). <math> One way to do this is by means of a convergent series of inverted rising exponentials. If <math>z^{\overline n} = z(z+1) \cdots (z+n-1)<math>, then

<math>\int_0^\infty \frac{2\arctan \frac{t}{z}}{\exp(2 \pi t)-1} \, dt

= \sum_{n=1}^\infty \frac{c_n}{(z+1)^{\overline n}}<math> where

<math>n c_n = \int_0^1 x^{\overline n}(x-\frac12)\, dx.<math>

From this we obtain a version of Stirling's series

<math>\ln \Gamma (z) = (z-\frac12)\ln z -z + \frac{\ln {2 \pi}}{2} + <math>
<math>\frac{1}{12(z+1)} + \frac{1}{12(z+1)(z+2)} + \frac{29}{60(z+1)(z+2)(z+3)} + \cdots<math>

which converges when <math>\Re(z)>0<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>. The more precise versions are due to Jacques Binet.

References

fr:Formule de Stirling it:Approssimazione di Stirling lt:Stirlingo formulė pl:Wzr Stirlinga scn:Formula di Stirling sv:Stirlings formel uk:Формула Стірлінґа

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools