PlanetMath: Stirling's approximation

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (23)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Entry average rating: No information on entry rating

Stirling's approximation

(Theorem)

Stirling's formula gives an approximation for , the factorial function. It is

$\displaystyle n! \approx \sqrt{2n\pi} n^n e^{-n}$

We can derive this from the gamma function. Note that for large ,

$\displaystyle \Gamma(x) = \sqrt{2\pi}x^{x-\frac{1}{2}} e^{-x + \mu(x)}$

(1)

where

$\displaystyle \mu(x) = \sum_{n=0}^\infty \left(x+ n +\frac{1}{2}\right) \ln \left(1+ \frac{1}{x+n} \right) -1 = \frac{\theta}{12x}$

with $0 < \theta < 1$ . Taking and multiplying by , we have

$\displaystyle n! = \sqrt{2\pi} n^{n+\frac{1}{2}} e^{-n + \frac{\theta}{12n}}$

(2)

Taking the approximation for large gives us Stirling's formula.

There is also a big-O notation version of Stirling's approximation:

$\displaystyle n! = \left(\sqrt{2\pi n}\right)\left(\frac{n}{e}\right)^n \left(1+\mathcal{O}\left(\frac{1}{n}\right)\right)$

(3)

We can prove this equality starting from (2). It is clear that the big-O portion of (3) must come from $e^{\frac{\theta}{12n}}$ , so we must consider the asymptotic behavior of .

First we observe that the Taylor series for is

$\displaystyle e^x = 1 + \frac{x}{1} + \frac{x^2}{2!} + \frac {x^3}{3!} + \cdots$

But in our case we have to a vanishing exponent. Note that if we vary as $\frac{1}{n}$ , we have as $n \longrightarrow \infty$

$\displaystyle e^x = 1 + \mathcal{O}\left(\frac{1}{n}\right)$

We can then (almost) directly plug this in to (2) to get (3) (note that the factor of 12 gets absorbed by the big-O notation.)

"Stirling's approximation" is owned by drini. [ full author list (4) | owner history (2) ]

(view preamble | get metadata)

Other names:

Stirling's formula, Stirling's approximation formula

Attachments:: asymptotic bounds for factorial (Result) by stevecheng
weaker version of Stirling's approximation (Result) by rm50

Log in to rate this entry.
(view current ratings)

Cross-references: factor, exponent, Taylor series, big-o, clear, equality, big-O notation, gamma function, factorial, approximation
There are 5 references to this entry.

This is version 18 of Stirling's approximation, born on 2001-11-17, modified 2006-11-03.
Object id is 953, canonical name is StirlingsApproximation.
Accessed 19397 times total.

Classification:

AMS MSC:	41A60 (Approximations and expansions :: Asymptotic approximations, asymptotic expansions )
	30E15 (Functions of a complex variable :: Miscellaneous topics of analysis in the complex domain :: Asymptotic representations in the complex domain)
	68Q25 (Computer science :: Theory of computing :: Analysis of algorithms and problem complexity)

Pending Errata and Addenda

None.[ View all 5 ]

Discussion

forum policy

No messages.

Interact