Stirling’s Formula
Stirling's Formula
February 5, 2014
Stirling's formula is a famous asymptotic formula to compute n!, the formula states
n n
n!
2n.
e
There are several ways to derive this formula, this note is meant to work on getting approximations to the formula without too much work. In this note we will use the following notation conventions for x a real number:
? x is the integer part of x, i.e., the largest integer less than or equal to x.
? {x} is the fractional part of x, i.e., {x} = x - x .
? A function f (x) is said to be O(g(x)) if there is a constant C such that f (x) C|g(x)| for large enough values of x.
f (x)
? A function f (x) is said to be o(g(x)) if lim
= 0.
xx g(x)
? log(x) is the natural logarithm of x, i.e., if y = log x then ex = y.
? N = {1, 2, 3, . . .} is the set of natural numbers. Stirling's formula is equivalent to
log (n!) = n log n - n + (1/2) log n + (1/2) log (2) + o(1).
In this note we will prove the following two theorems:
Theorem 1. For n N, log (n!) = n log n - n + O(log n).
Theorem 2. For n N, log (n!) = n log n - n + (1/2) log n + O(1).
A quick corollary of Theorem 2 is that
n n
n! = O
n.
e
Proof of Theorem 1. Because log (ab) = log a + log b we have
n
log (n!) = log 1 + log 2 + log 3 + . . . + log n = log n log t dt.
kn
1
1
By using a left Riemann sum on
n 1
log
t
dt
we
have
n
(log 1 + log 2 + log 3 + . . . + log (n - 1)) + log n
log t dt + log n
1
= n log n - n + 1 + log n
= n log n - n + O(log n).
On the other hand using a right Riemann sum we get
n
log 2 + log 3 + log 4 + . . . + log n log t dt = n log n - n.
1
Therefore n log n - n log (n!) n log n - n + 1 + log n, and hence log (n!) = n log n - n + O(log n).
To prove the second theorem we'll use the following useful result known as "partial summation" or "Abel summation":
Proposition 1 (Abel summation). Let {an} be a sequence and let f : R R be a differentiable function. Define A(x) to be
A(x) = an = a1 + a2 + a3 + . . . + a x .
nx
Partial summation is the following identity:
b
anf (n) = A(b)f (b) - A(a)f (a) - A(t)f (t) dt.
anb
a
Proof of Theorem 2. As stated before
log (n!) =
log k.
1kn
Using Abel summation with an = 1 and f (n) = log n we have
nt
log k = n log n - 1 log 1 -
dt
1kn
1t
n t - {t}
= n log n -
dt
1
t
n {t}
= n log n - n + 1 +
dt
1t
n {t}
= n log n - n +
dt + O(1).
1t
Therefore proving the theorem comes down to proving that
n {t}
1
dt = log n + O(1),
1t
2
2
which boils down to proving
n {t} - 1/2
dt = O(1).
(1)
1
t
We'll finish by proving (1). We'll break the integral into n - 1 parts, so that we can be
able to get a grip on {t}:
n {t} - 1/2
n-1 k+1 {t} - 1/2
dt =
dt.
1
t
k=1 k
t
Now let's perform the change of variable t t - k in the inner integral:
k+1 {t} - 1/2
1 t - 1/2
dt =
dt
k
t
0 t+k
11
= 1 - (k + 1/2)
dt
0 t+k
k+1 = 1 - (k + 1/2) log
k
1 = 1 - (k + 1/2) log 1 + .
k
We now use the Taylor series for log (1 + x) = x - x2/2 + x3/3 - . . . to get:
1
1
111
k + log 1 + = k +
- +...
2
k
2 k 2k2
11
11
= 1- + -...+ - +...
2k 3k2
2k 4k2
11
11
11
=1+
-
-
-
+
-
...
3k2 4k2
4k3 6k3
5k4 8k4
1
1
3
= 1+ - + -...
12k2 12k3 40k4
1
=1+O
.
k2
Therefore,
n {t} - 1/2
n-1
dt =
1
t
k=1
n-1
k+1 {t} - 1/2
dt
k
t
=
1 - (k + 1/2) log
k=1
n-1
1
= O k2 = O(1).
k=1
1 1+
k
3
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- b 5 properties of logarithms 1b jmap
- fall17 hw04 — semilog and double log plots
- m6 algebra ii trigonometry name
- sec 3 2 2 b7 falling off a log
- differentiating logarithmic functions
- maths genie free online gcse and a level maths revision
- solving exponential and logarithmic equations
- use properties of logarithms to expand logarithmic
- exponentials and logarithms 14f
- stirling s formula
Related searches
- the cleaner 7 day women s formula revie
- the cleaner 7 day women s formula reviews
- the cleaner men s formula review
- the cleaner women s formula gnc
- the formula for newton s 2nd law
- newton s law formula sheet
- formula for newton s second law
- today s date formula in excel
- formula for today s date in excel
- euclid s formula gcd
- the 3 p s formula for success
- formula for pearson s correlation coefficient