The Stirling's approximation [1] states that ∀ n ∈ N + \forall n \in \mathbb{N}^+ ∀ n ∈ N +
2 π n ( n e ) n e 1 12 n + 1 ≤ n ! ≤ 2 π n ( n e ) n e 1 12 n .
\sqrt{2 \pi} \sqrt{n} \left( \frac{n}{e} \right)^n e^{ \frac{1}{ 12n + 1 } } \le n! \le \sqrt{2 \pi} \sqrt{n} \left( \frac{n}{e} \right)^n e^{ \frac{1}{ 12n } }.
2 π n ( e n ) n e 12 n + 1 1 ≤ n ! ≤ 2 π n ( e n ) n e 12 n 1 . As ∀ x ∈ R , e x ≥ 1 + x \forall x \in R, e^x \ge 1 + x ∀ x ∈ R , e x ≥ 1 + x 0 < x < 0.5 0 < x < 0.5 0 < x < 0.5 e x ≤ 1 + 2 x e^x \le 1 + 2 x e x ≤ 1 + 2 x ∀ n ∈ N + \forall n \in \mathbb{N}^+ ∀ n ∈ N +
2 π n ( n e ) n ( 1 + 1 12 n + 1 ) ≤ n ! ≤ 2 π n ( n e ) n ( 1 + 1 6 n ) .
\sqrt{2 \pi} \sqrt{n} \left( \frac{n}{e} \right)^n \left( 1 + \frac{1}{ 12n + 1 } \right) \le n! \le \sqrt{2 \pi} \sqrt{n} \left( \frac{n}{e} \right)^n \left( 1 + \frac{1}{ 6n } \right).
2 π n ( e n ) n ( 1 + 12 n + 1 1 ) ≤ n ! ≤ 2 π n ( e n ) n ( 1 + 6 n 1 ) . Asymptotically,
n ! = 2 π n ( n e ) n ( 1 + Θ ( 1 n ) ) .
n! = \sqrt{2 \pi} \sqrt{n} \left( \frac{n}{e} \right)^n \left( 1 + \Theta \left( \frac{1}{n} \right) \right).
n ! = 2 π n ( e n ) n ( 1 + Θ ( n 1 ) ) . In the remainder of the blog, we try to approach this estimation incrementally. First we have two trivial facts.
1. n ! ≤ n n n! \le n^n n ! ≤ n n
2. n ! ≥ ( n / 2 ) n / 2 n! \ge (n / 2)^{n / 2} n ! ≥ ( n /2 ) n /2
Proof: Clearly this holds for even numbers. When n n n ⌈ n / 2 ⌉ = ( n + 1 ) / 2 \lceil n / 2 \rceil = (n + 1) / 2 ⌈ n /2 ⌉ = ( n + 1 ) /2 ( n + 1 ) / 2 (n + 1) / 2 ( n + 1 ) /2 [ n ] [n] [ n ] ≥ ( n + 1 ) / 2 \ge (n + 1) / 2 ≥ ( n + 1 ) /2
n ! ≥ ∏ i = ( n + 1 ) / 2 ) n i ≥ ( ( n + 1 ) / 2 ) ) ( n + 1 ) / 2 ) ≥ ( n / 2 ) n / 2
n! \ge \prod_{i = (n + 1) / 2)}^n i \ge \big( (n + 1) / 2) \big)^{ (n + 1) / 2) } \ge (n / 2)^{n / 2}
n ! ≥ i = ( n + 1 ) /2 ) ∏ n i ≥ ( ( n + 1 ) /2 ) ) ( n + 1 ) /2 ) ≥ ( n /2 ) n /2 □ \square □
Somewhat unexpectedly, we can combine inequality (1) and (2) to obtain the asymptotical trend of log n ! \log n! log n !
( n / 2 ) log 2 n − ( n / 2 ) ≤ log 2 n ! ≤ n log 2 n .
(n / 2) \log_2 n - (n / 2) \le \log_2 n! \le n \log_2 n.
( n /2 ) log 2 n − ( n /2 ) ≤ log 2 n ! ≤ n log 2 n . This implies that
log 2 n ! = Θ ( n log n ) .
\log_2 n! = \Theta( n \log n).
log 2 n ! = Θ ( n log n ) . We proceed to get even sharper bounds.
3. n ! ≥ n n exp ( n ) = ( n / e ) n n! \ge \frac{n^n}{ \exp(n) } = (n / e)^n n ! ≥ e x p ( n ) n n = ( n / e ) n
Proof: Using the Taylor expansion for exp ( x ) \exp(x) exp ( x ) ∀ x ∈ R \forall x \in \mathbb{R} ∀ x ∈ R
exp ( x ) = 1 + x + x 2 2 ! + . . . + x n n ! + . . .
\exp(x) = 1 + x + \frac{x^2}{2!} + ... + \frac{x^n}{n!} + ...
exp ( x ) = 1 + x + 2 ! x 2 + ... + n ! x n + ... Keeping only the n n n
n ! ≥ x n exp ( x ) .
n! \ge \frac{x^n}{\exp(x) }.
n ! ≥ exp ( x ) x n . Taking x = n x = n x = n
□ \square □
4. n ! ≥ e ( n / e ) n n! \ge e ( n / e)^n n ! ≥ e ( n / e ) n
Proof: Using the Taylor expansion for exp ( x ) \exp(x) exp ( x ) ∀ x ∈ R \forall x \in \mathbb{R} ∀ x ∈ R
exp ( x ) = 1 + x + x 2 2 ! + . . . + x n n ! + . . .
\exp(x) = 1 + x + \frac{x^2}{2!} + ... + \frac{x^n}{n!} + ...
exp ( x ) = 1 + x + 2 ! x 2 + ... + n ! x n + ... Setting x = n x = n x = n
exp ( n ) ≥ n n − 1 ( n − 1 ) ! + n n n ! = 2 n n n ! ,
\exp(n) \ge \frac{n^{n - 1} }{ (n - 1)!} + \frac{ n^n }{n !} = 2 \frac{ n^n }{n !},
exp ( n ) ≥ ( n − 1 )! n n − 1 + n ! n n = 2 n ! n n , which finishes our proof.
□ \square □
Next we resort to calculus to get finer estimation.
5. n ! ≥ e ( n / e ) n n! \ge e ( n / e)^n n ! ≥ e ( n / e ) n
Proof: As the figure below shows, ∑ i ∈ [ n ] ln i \sum_{i \in [n] } \ln i ∑ i ∈ [ n ] ln i y = log t y = \log t y = log t
∑ i ∈ [ n ] ln i ≥ ∫ 1 n ln t d t = t ln t ∣ 1 n − ∫ 1 n 1 d t = n ln n − n + 1.
\sum_{i \in [n]} \ln i \ge \int_1^n \ln t \ dt = t \ln t \mid_1^n - \int_1^n 1 \ dt = n \ln n - n + 1.
i ∈ [ n ] ∑ ln i ≥ ∫ 1 n ln t d t = t ln t ∣ 1 n − ∫ 1 n 1 d t = n ln n − n + 1. Hence, n ! ≥ e ( n / e ) n n! \ge e (n / e)^n n ! ≥ e ( n / e ) n
□ \square □
6. n ! ≤ e n ( n / e ) n n! \le e \sqrt{n} (n / e)^n n ! ≤ e n ( n / e ) n
Proof: For a rectangle, its area can be decomposed into the curvilinear area under y = ln t y = \ln t y = ln t ∑ i ∈ [ n ] ln i \sum_{i \in [n] } \ln i ∑ i ∈ [ n ] ln i
How are we going to do that? Image that we put a wall at t = 1 t = 1 t = 1 1 1 1 ln n \ln n ln n
∑ i ∈ [ n ] ln i ≤ ∫ 1 n ln t d t + 1 2 ln n = n ln n − n + 1 + 1 2 ln n .
\sum_{i \in [n]} \ln i \le \int_1^n \ln t \ dt + \frac{1}{2} \ln n = n \ln n - n + 1 + \frac{1}{2} \ln n.
i ∈ [ n ] ∑ ln i ≤ ∫ 1 n ln t d t + 2 1 ln n = n ln n − n + 1 + 2 1 ln n .
□ \square □
By inequality (4) and (5), we get
e ( n / e ) n ≤ n ! ≤ e n ( n / e ) n .
e ( n / e)^n \le n! \le e \sqrt{n} (n / e)^n.
e ( n / e ) n ≤ n ! ≤ e n ( n / e ) n . So
n ! = Θ ( ( n / e ) n ) .
n! = \Theta ( (n / e)^n ).
n ! = Θ (( n / e ) n ) . Indeed the approximation of e n ( n / e ) n e \sqrt n (n / e)^n e n ( n / e ) n 2 π n ( n / e ) n \sqrt{2 \pi} \sqrt n (n / e)^n 2 π n ( n / e ) n
e n ( n / e ) n 2 π n ( n / e ) n = e 2 π ≈ 1.084.
\frac{ e \sqrt n (n / e)^n }{ \sqrt{2 \pi} \sqrt n (n / e)^n } = \frac{e }{\sqrt{ 2 \pi} } \approx 1.084.
2 π n ( n / e ) n e n ( n / e ) n = 2 π e ≈ 1.084. Therefore, when n n n e n ( n / e ) n e \sqrt n (n / e)^n e n ( n / e ) n 10 % 10\% 10% n ! n! n !
7. n ! ≤ e n ( n / e ) n n! \le e \sqrt{n} (n / e)^n n ! ≤ e n ( n / e ) n
The same inequality can be obtained in the following manner.
Proof: We lower bound the integral by the areas of trapezoids. The trapezoid between t t t t + 1 t + 1 t + 1 ln t \ln t ln t ln ( t + 1 ) \ln (t + 1) ln ( t + 1 ) 1 2 ( ln t + ln ( t + 1 ) ) \frac{1}{2} (\ln t + \ln (t + 1) ) 2 1 ( ln t + ln ( t + 1 ))
∑ i = 1 n ln i = 1 2 ∑ t = 1 n − 1 ( ln t + ln ( t + 1 ) ) + 1 2 ln n ≤ ∫ 1 n ln t d t + 1 2 ln n = n ln n − n + 1 + 1 2 ln n
\begin{aligned}
\sum_{i = 1}^n \ln i &= \frac{1}{2} \sum_{t = 1}^{n - 1} (\ln t + \ln (t + 1) ) + \frac{1}{2} \ln n \\
&\le \int_1^n \ln t \ dt + \frac{1}{2} \ln n \\
&= n \ln n - n + 1 + \frac{1}{2} \ln n
\end{aligned}
i = 1 ∑ n ln i = 2 1 t = 1 ∑ n − 1 ( ln t + ln ( t + 1 )) + 2 1 ln n ≤ ∫ 1 n ln t d t + 2 1 ln n = n ln n − n + 1 + 2 1 ln n
□ \square □
8. n ! ∈ [ e 11 / 12 n ( n e ) n e 1 / ( 12 n + 1 ) , e 12 / 13 n ( n e ) n e 1 / ( 12 n ) ] n! \in [e^{11 / 12} \sqrt{n} \left( \frac{n}{e} \right)^n e^{ 1 / (12n + 1)}, e^{12 / 13} \sqrt{n} \left( \frac{n}{e} \right)^n e^{1 / (12 n) }] n ! ∈ [ e 11/12 n ( e n ) n e 1/ ( 12 n + 1 ) , e 12/13 n ( e n ) n e 1/ ( 12 n ) ]
Proof: Let
U k = ∫ k k + 1 ln t d t , L k = 1 2 ( ln k + ln ( k + 1 ) ) .
\begin{aligned}
U_k &= \int_k^{k + 1} \ln t \ dt, \\
L_k &= \frac{1}{2} \left(\ln k + \ln (k + 1) \right).
\end{aligned}
U k L k = ∫ k k + 1 ln t d t , = 2 1 ( ln k + ln ( k + 1 ) ) . The estimation error in the previous section is determined by the gap between U k U_k U k L k L_k L k k ∈ [ n − 1 ] k \in [n - 1] k ∈ [ n − 1 ] ∀ k ∈ [ n − 1 ] \forall k \in [n - 1] ∀ k ∈ [ n − 1 ]
ϵ k ≐ U k − L k .
\epsilon_k \doteq U_k - L_k .
ϵ k ≐ U k − L k . Denote S = ∑ i ∈ [ n ] ln i S = \sum_{i \in [n] } \ln i S = ∑ i ∈ [ n ] ln i S ^ = n ln n − n + 1 + 1 2 ln n \hat S = n \ln n - n + 1 + \frac{1}{2} \ln n S ^ = n ln n − n + 1 + 2 1 ln n
S ^ − S = ∑ i = 1 n − 1 ϵ k .
\hat S - S = \sum_{i = 1}^{n - 1} \epsilon_k.
S ^ − S = i = 1 ∑ n − 1 ϵ k . For a fixed k k k ϵ k \epsilon_k ϵ k
ϵ k = t ln t ∣ k k + 1 − t ∣ k k + 1 − 1 2 ( ln k + ln ( k + 1 ) ) = ln ( k + 1 ) k + 1 k k ⋅ 1 k 1 2 ( k + 1 ) 1 2 − 1 = ln ( k + 1 k ) k + 1 2 − 1 = ( 2 k + 1 2 ) ⋅ ln ( k + 1 k ) − 1
\begin{aligned}
\epsilon_k
&= t \ln t \mid_k^{k + 1} - t \mid_k^{k + 1} - \frac{1}{2} \left( \ln k + \ln (k + 1) \right) \\
&= \ln \frac{ (k + 1)^{k + 1} }{ k^k } \cdot \frac{1}{ k^{\frac{1}{2} } (k + 1)^{\frac{1}{2} } } - 1 \\
&= \ln \left( \frac{k + 1}{k } \right)^{ k + \frac{1}{2} } - 1 \\
&= \left( \frac{2k + 1}{2} \right) \cdot \ln \left( \frac{k + 1}{k } \right)- 1 \\
\end{aligned}
ϵ k = t ln t ∣ k k + 1 − t ∣ k k + 1 − 2 1 ( ln k + ln ( k + 1 ) ) = ln k k ( k + 1 ) k + 1 ⋅ k 2 1 ( k + 1 ) 2 1 1 − 1 = ln ( k k + 1 ) k + 2 1 − 1 = ( 2 2 k + 1 ) ⋅ ln ( k k + 1 ) − 1 Let x = 1 2 k + 1 x = \frac{1}{2k + 1} x = 2 k + 1 1 k + 1 = 1 2 ( ( 2 k + 1 ) + 1 ) k + 1 = \frac{1}{2}( (2k + 1) + 1) k + 1 = 2 1 (( 2 k + 1 ) + 1 ) k = 1 2 ( ( 2 k + 1 ) − 1 ) k = \frac{1}{2}( (2k + 1) - 1) k = 2 1 (( 2 k + 1 ) − 1 )
ϵ k = ( 2 k + 1 2 ) ⋅ ln ( 1 + k k ) − 1 = 1 2 x ln 1 + x 1 − x − 1.
\epsilon_k = \left( \frac{2k + 1}{2} \right) \cdot \ln \left( \frac{1 + k }{k } \right)- 1 = \frac{1}{2 x} \ln \frac{1 + x}{1 - x} - 1.
ϵ k = ( 2 2 k + 1 ) ⋅ ln ( k 1 + k ) − 1 = 2 x 1 ln 1 − x 1 + x − 1. Using the Taylor's expansions for y = ln ( 1 − x ) y = \ln(1 -x) y = ln ( 1 − x ) y = ln ( 1 + x ) y = \ln(1 + x) y = ln ( 1 + x )
ln ( 1 − x ) = − ( x + x 2 2 + x 3 3 + . . . ) ln ( 1 + x ) = − ( − x + x 2 2 − x 3 3 + . . . )
\ln(1 - x) = -(x + \frac{x^2}{2} + \frac{x^3}{3} + ...) \\
\ln(1 + x) = -(-x + \frac{x^2}{2} - \frac{x^3}{3} + ...) \\
ln ( 1 − x ) = − ( x + 2 x 2 + 3 x 3 + ... ) ln ( 1 + x ) = − ( − x + 2 x 2 − 3 x 3 + ... ) and
ln 1 + x 1 − x = 2 ( x + x 3 3 + x 5 5 + x 7 7 + . . . ) .
\ln \frac{1 + x}{1 - x} = 2 (x + \frac{x^3}{3} + \frac{x^5}{5} + \frac{x^7}{7} + ... ).
ln 1 − x 1 + x = 2 ( x + 3 x 3 + 5 x 5 + 7 x 7 + ... ) . It follows that
ϵ k = x 2 3 + x 4 5 + x 6 7 + . . .
\epsilon_k = \frac{x^2}{3} + \frac{x^4}{5} + \frac{x^6}{7} + ...
ϵ k = 3 x 2 + 5 x 4 + 7 x 6 + ... We can upper bound ϵ k \epsilon_k ϵ k
ϵ k ≤ x 2 3 ( 1 + x 2 + x 4 + . . . ) = x 2 3 1 1 − x 2 = 1 3 1 ( 2 k + 1 ) 2 − 1 = 1 12 ( 1 k − 1 k + 1 ) .
\begin{aligned}
\epsilon_k
&\le \frac{x^2}{3} ( 1 + x^2 +x^4 + ... ) \\
&= \frac{x^2}{3} \frac{1}{1 - x^2} \\
&= \frac{1}{3} \frac{1}{ (2k + 1)^2 - 1} \\
&= \frac{1}{12} \left(\frac{1}{k } - \frac{1}{k + 1} \right).
\end{aligned}
ϵ k ≤ 3 x 2 ( 1 + x 2 + x 4 + ... ) = 3 x 2 1 − x 2 1 = 3 1 ( 2 k + 1 ) 2 − 1 1 = 12 1 ( k 1 − k + 1 1 ) . Also, we can lower bound ϵ k \epsilon_k ϵ k
ϵ k ≥ x 2 3 ( 1 + x 2 / 3 + x 4 / 3 2 + . . . ) = x 2 3 1 1 − x 2 / 3 = 1 3 ( 2 k + 1 ) 2 − 1 = 1 12 ( k 2 + k + 2 12 ) ≥ 1 12 ( k + 1 + 1 12 ) ( k + 1 12 ) = 1 12 ( 1 k + 1 12 − 1 k + 1 + 1 12 ) .
\begin{aligned}
\epsilon_k
&\ge \frac{x^2}{3} ( 1 + x^2 / 3 +x^4 / 3^2 + ... ) \\
&= \frac{x^2}{3} \frac{1}{1 - x^2 / 3} \\
&= \frac{1}{ 3(2k + 1)^2 - 1} \\
&= \frac{1}{ 12(k^2 + k + \frac{2}{12} ) } \\
&\ge \frac{1}{ 12(k + 1 + \frac{1}{12}) ( k + \frac{1}{12} ) } \\
&= \frac{1}{12} \left(\frac{1}{k + \frac{1}{12} } - \frac{1}{k + 1 + \frac{1}{12} } \right).
\end{aligned}
ϵ k ≥ 3 x 2 ( 1 + x 2 /3 + x 4 / 3 2 + ... ) = 3 x 2 1 − x 2 /3 1 = 3 ( 2 k + 1 ) 2 − 1 1 = 12 ( k 2 + k + 12 2 ) 1 ≥ 12 ( k + 1 + 12 1 ) ( k + 12 1 ) 1 = 12 1 ( k + 12 1 1 − k + 1 + 12 1 1 ) . Let A = ∑ k = 1 ∞ ϵ k A = \sum_{k = 1}^\infty \epsilon_k A = ∑ k = 1 ∞ ϵ k R = ∑ k = n ∞ ϵ k R = \sum_{k = n}^\infty \epsilon_k R = ∑ k = n ∞ ϵ k
S ^ − S = A − R ⟹ S = S ^ − A + R ⟹ S = n ln n − n + 1 + 1 2 ln n − A + R ⟹ n ! = e 1 − A n ( n e ) n e R .
\begin{aligned}
\hat S - S &= A - R \\
\implies S &= \hat S - A + R \\
\implies S &= n \ln n - n + 1 + \frac{1}{2} \ln n - A + R \\
\implies n! &= e^{1 - A} \sqrt{n} \left( \frac{n}{e} \right)^n e^R.
\end{aligned}
S ^ − S ⟹ S ⟹ S ⟹ n ! = A − R = S ^ − A + R = n ln n − n + 1 + 2 1 ln n − A + R = e 1 − A n ( e n ) n e R . By previous inequalities, we know
A ≥ 1 12 ∑ k = 1 ∞ ( 1 k + 1 12 − 1 k + 1 + 1 12 ) = 1 12 1 1 + 1 12 = 1 13 A ≤ 1 12 ∑ k = 1 ∞ ( 1 k − 1 k + 1 ) = 1 12 .
\begin{aligned}
A &\ge \frac{1}{12} \sum_{k = 1}^\infty \left( \frac{1}{k + \frac{1}{12} } - \frac{1}{k + 1 + \frac{1}{12} } \right) = \frac{1}{12} \frac{1}{1 + \frac{1}{12} } = \frac{1}{13} \\
A &\le \frac{1}{12} \sum_{k = 1}^\infty \left(\frac{1}{k } - \frac{1}{k + 1} \right) = \frac{1}{12}.
\end{aligned}
A A ≥ 12 1 k = 1 ∑ ∞ ( k + 12 1 1 − k + 1 + 12 1 1 ) = 12 1 1 + 12 1 1 = 13 1 ≤ 12 1 k = 1 ∑ ∞ ( k 1 − k + 1 1 ) = 12 1 . Similarly, we can get 1 12 n + 1 = 1 12 1 n + 1 12 ≤ R ≤ 1 12 n \frac{1}{12n + 1 } = \frac{1}{12} \frac{1}{n + \frac{1}{12} } \le R \le \frac{1}{12n} 12 n + 1 1 = 12 1 n + 12 1 1 ≤ R ≤ 12 n 1
n ! ∈ [ e 11 / 12 n ( n e ) n e 1 / ( 12 n + 1 ) , e 12 / 13 n ( n e ) n e 1 / ( 12 n ) ]
n! \in [e^{11 / 12} \sqrt{n} \left( \frac{n}{e} \right)^n e^{ 1 / (12n + 1)}, e^{12 / 13} \sqrt{n} \left( \frac{n}{e} \right)^n e^{1 / (12 n) }]
n ! ∈ [ e 11/12 n ( e n ) n e 1/ ( 12 n + 1 ) , e 12/13 n ( e n ) n e 1/ ( 12 n ) ] □ \square □
Reference
[1] H. Robbins, “A Remark on Stirling’s Formula,” The American Mathematical Monthly, vol. 62, no. 1, pp. 26–29, 1955
← Back to all notes Back to top ↑ 
