Stirling's Approximation Website Links For
Approximation 		 

Information About

Stirling's Approximation
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



In Mathematics , Stirling's approximation (or '''Stirling's formula''') is an approximation for large Factorial s. It is named in honour of James Stirling .

The formula is written as:

::\ln n! \cong n \ln n - n \,

for any sufficiently large integer ''n'', where ''ln'' is the Natural Logarithm function. (The Gamma function formulation described below is the equivalent approximation for non-integers).


FORMAL DEFINITION

More formally, Stirling's approximation is
::\lim_{n ightarrow \infty} {n!\over \sqrt{2 \pi n} \; \left( rac{n}{e} ight)^{n} } = 1
:(See Limit , Square Root , π , E .)

which is often written as
::n! \cong \sqrt{2 \pi n} \; \left( rac{n}{e} ight)^{n}


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 + \ldots + \ln n

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

:\ln (n-1)! = n \ln n - n + 1 - rac{\ln n}{2} + \sum_{k=2}^{m} rac{B_k {(-1)}^k}{k(k-1)} \left( rac{1}{n^{k-1}} - 1 ight) + R

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

We can then take limits on both sides,

:\lim_{n o \infty} \left( \ln n! - n \ln n + n - rac{\ln n}{2} ight) = 1 + \sum_{k=2}^{m} rac{B_k {(-1)}^k}{k(k-1)} + \lim_{n o \infty} R

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

:\ln n! = \left( n+ rac{1}{2} ight) \ln n - n + y + \sum_{k=2}^{m} rac{B_k {(-1)}^k}{k(k-1)n^{k-1}} + O \left( rac{1}{n^m} ight)

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.

:n! = e^y \sqrt{n}~{\left( rac{n}{e} ight)}^n \left( 1 + O \left( rac{1}{n} ight) ight)

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 \sqrt{2 \pi}. Therefore, we get Stirling's formula:

:n! = \sqrt{2 \pi n}~{\left( rac{n}{e} ight)}^n \left( 1 + O \left( rac{1}{n} ight) ight)

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,
:n! = \sqrt{2 \pi n} \; \left( rac{n}{e} ight)^{n}e^{\lambda_n}
with
: rac{1}{12n+1} < \lambda_n < rac{1}{12n}.

Stirling's formula is in fact the first approximation to the following series (now called the Stirling series):
:
n!=\sqrt{2\pi n}\left({n\over e} ight)^n
\left(
1
+{1\over12n}
+{1\over288n^2}
-{139\over51840n^3}
-{571\over2488320n^4}
+ \cdots
ight)


As n o \infty, 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'':

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


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
:\Gamma(z+1) = \Pi(z) = z!
defined for all complex numbers other than non-positive integers. If
\Re(z) > 0 then
:\ln \Gamma (z) = (z- rac12)\ln z -z + rac{\ln {2 \pi}}{2} + 2 \int_0^\infty rac{\arctan rac{t}{z}}{\exp(2 \pi t)-1} dt
Repeated integration by parts gives the asymptotic expansion
:\ln \Gamma (z) = (z- rac12)\ln z -z + rac{\ln {2 \pi}}{2} + \sum_{n=1}^\infty rac{B_{2n}}{2n(2n-1)z^{2n-1}}


= \ln\Gamma (z) - \left( z- rac12 ight) \ln z +z - rac12\ln(2\pi).
One way to do this is by means of a convergent series of inverted Rising Exponentials . If z^{\overline n} = z(z+1) \cdots (z+n-1), then
:\int_0^\infty rac{2\arctan rac{t}{z}}{\exp(2 \pi t)-1} \, dt
= \sum_{n=1}^\infty rac{c_n}{(z+1)^{\overline n}}
where
: c_n = rac{1}{n} \int_0^1 x^{\overline n} \left( x- rac12 ight) \, dx.
From this we obtain a version of Stirling's series
:\ln \Gamma (z) = \left( z- rac12 ight) \ln z -z + rac{\ln {2 \pi}}{2}
:::{} + rac{1}{12(z+1)} + rac{1}{12(z+1)(z+2)} + rac{59}{360(z+1)(z+2)(z+3)} + rac{29}{60(z+1)(z+2)(z+3)(z+4)} + \cdots
which converges when \Re(z)>0.


A VERSION SUITABLE FOR CALCULATORS

The approximation

:\Gamma(z) \cong \sqrt{ rac{2 \pi}{z} } \left( rac{z}{e} \sqrt{ z \sinh rac{1}{z} \left + rac{1}{810z^6} ight } ight)^{z},

or equivalently,

:2 \ln \Gamma(z) \cong \ln(2 \pi) - \ln z + z \left(3 \ln z + \ln \left(\sinh rac{1}{z} \left + rac{1}{810z^6} ight ight) - 2 ight),

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. The term in square brackets is optional and increases accuracy slightly; even without it, this approximation is good to more than 8 decimal digits for ''z'' with a real part greater than 8. Viktor Toth (2004) suggests it for computing the Gamma function with fair accuracy on calculators with limited program or register memory.


HISTORY

The formula was first discovered by Abraham De Moivre in the form
:n!\sim [{ m constant}]\cdot n^{n+1/2} e^{-n}
Stirling's contribution consisted of showing that the constant
is \sqrt{2\pi}. The more precise versions are due to
Jacques Binet .


REFERENCES