Information Technology Reference
In-Depth Information
k
B
k
=
{{
(
n
+
B
)
−
}}
∑
i
=
1
,
n
i
k
−
1
.
k
7.5
Stirling Approximation
The approximation of
n
! which we prove in this section, due to Stirling, is a key
point in many contexts of discrete mathematics.
Theorem 7.12 (Stirling Approximation).
→
n
→
∞
√
2
n
n
!
π
n
(
n
/
e
)
Proof.
Let us consider the ratio
n
n
/
n
!, then
n
n
·
n
n
n
1
.
n
n
/
n
!
=
1
·
2
·...
n
−
n
−
Of course:
n
n
n
−
1
n
−
2
n
−
i
+
1
i
.
If we replace its left member with the right one, in the initial equation, then we get:
i
=
1
·
2
·
3
·
n
−
n
−
n
−
n
−
n
−
n
n
n
n
n
n
n
n
n
−
1
−
1
−
2
n
n
/
n
!
=
...
−
1
−
1
n
−
2
−
1
n
−
2
n
−
3
whence, by grouping in decreasing order:
n
n
n
−
1
n
n
−
2
n
n
−
3
−
1
−
2
n
n
/
n
!
=
...
−
1
n
−
2
n
−
3
that is:
1
n
−
i
n
1
i
=
1
−
1
n
n
/
n
!
=
+
n
−
i
where each factor seems to go to Euler constant
e
when
n
goes to infinity, by sug-
gesting this (wrong) equation:
n
n
n
!
e
n
−
1
≈
(wrong)
This evaluation is wrong because these factors do not tend to
e
simultaneously. In
fact, when the first one is near to
e
, the last one has to start its approximation. In order
to get a better evaluation we define the following term
b
(
)
n
by trying to evaluate its
asymptotic behavior:
e
n
n
!
n
n
/
=
b
(
n
)
.
