TAOCP 1.2.11.2 Exercise 5
Assume n!
Section 1.2.11.2: Euler's Summation Formula
Exercise 5. [HM30] Given that
$$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right), $$
show that $\kappa=\sqrt{2\pi}$ by using Wallis's product.
Verified: yes
Solve time: 59s
Setup
Assume
$$ n! = \kappa \sqrt{n}\left(\frac{n}{e}\right)^n\left(1+O!\left(\frac{1}{n}\right)\right) \tag{1} $$
for a constant $\kappa>0$.
Define the central binomial coefficient
$$ \binom{2n}{n} = \frac{(2n)!}{(n!)^2}. \tag{2} $$
Substituting (1) into (2) gives an asymptotic expression for $\binom{2n}{n}$ in terms of $\kappa$.
Wallis’s product implies the classical asymptotic relation
$$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}}\left(1+O!\left(\frac{1}{n}\right)\right). \tag{3} $$
The task is to determine $\kappa$ by comparing (2) with (3).
Solution
From (1),
$$ (2n)! = \kappa \sqrt{2n}\left(\frac{2n}{e}\right)^{2n}\left(1+O!\left(\frac{1}{n}\right)\right). \tag{4} $$
Also,
$$ (n!)^2 = \kappa^2 n \left(\frac{n}{e}\right)^{2n}\left(1+O!\left(\frac{1}{n}\right)\right), \tag{5} $$
since multiplying two factors of the form $1+O(1/n)$ preserves the same order of error.
Dividing (4) by (5) yields
$$ \binom{2n}{n} = \frac{\kappa \sqrt{2n}}{\kappa^2 n} \cdot \frac{(2n)^{2n}}{n^{2n}} \cdot \left(1+O!\left(\frac{1}{n}\right)\right). \tag{6} $$
Each factor is simplified separately.
First,
$$ \frac{\kappa \sqrt{2n}}{\kappa^2 n} = \frac{\sqrt{2}}{\kappa \sqrt{n}}. \tag{7} $$
Second,
$$ \frac{(2n)^{2n}}{n^{2n}} = 2^{2n} = 4^n. \tag{8} $$
Substituting (7) and (8) into (6) gives
$$ \binom{2n}{n} = \frac{4^n}{\sqrt{n}} \cdot \frac{\sqrt{2}}{\kappa} \left(1+O!\left(\frac{1}{n}\right)\right). \tag{9} $$
From Wallis’s product, the central binomial coefficient satisfies
$$ \binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} \left(1+O!\left(\frac{1}{n}\right)\right). \tag{10} $$
Comparing the leading constant factors in (9) and (10) gives
$$ \frac{\sqrt{2}}{\kappa} = \frac{1}{\sqrt{\pi}}. \tag{11} $$
Solving (11) yields
$$ \kappa = \sqrt{2\pi}. $$
This completes the proof. ∎
Verification
From (9), the dependence on $n$ in the leading term is $4^n n^{-1/2}$, matching the structure in (10). The remaining multiplicative constant in (9) is $\sqrt{2}/\kappa$, and in (10) it is $1/\sqrt{\pi}$. Equality of asymptotic expressions requires equality of these constants, since any discrepancy would produce a nonvanishing multiplicative factor in the ratio of the two sides as $n \to \infty$.
Notes
Wallis’s product
$$ \prod_{k=1}^{\infty} \frac{4k^2}{4k^2-1} = \frac{\pi}{2} $$
is equivalent to (10) through standard finite truncation identities for central binomial coefficients. The constant $\kappa$ is therefore determined uniquely by consistency between Stirling-type asymptotics and the evaluation of $\pi$ via Wallis’s infinite product.