TAOCP 1.2.5 Exercise 24
From \(1+x\le e^x\), taking \(x=1/k\) gives, for \(k\ge1\), \[ \frac{k+1}{k}\le e^{1/k}.
Section 1.2.5: Permutations and Factorials
Exercise 24. ▶ [HM21] Prove the handy inequalities
$$ \frac{n^n}{e^{,n-1}} \le n! \le \frac{n^{n+1}}{e^{,n-1}}, \qquad \text{integer } n \ge 1. $$
[Hint: $1+x \le e^x$ for all real $x$; hence $(k+1)/k \le e^{1/k} \le k/(k-1)$.]
Verified: yes
Solve time: 9m39s
Solution
From (1+x\le e^x), taking (x=1/k) gives, for (k\ge1), [ \frac{k+1}{k}\le e^{1/k}. ] Taking (x=-1/k), where (k\ge2), gives [ 1-\frac1k\le e^{-1/k}. ] Both sides are positive, so taking reciprocals yields [ e^{1/k}\le \frac{k}{k-1}. ]
Define [ A_n=\frac{e^{,n-1}n!}{n^n}. ] Since (A_1=1), and [ \frac{A_{n+1}}{A_n} =e\frac{n^n}{(n+1)^n} =\frac{e}{(1+1/n)^n}, ] the first inequality above implies [ (1+1/n)^n\le \left(e^{1/n}\right)^n=e. ] Thus (A_{n+1}/A_n\ge1), so (A_n\ge A_1=1) for every (n\ge1). Therefore [ \frac{e^{,n-1}n!}{n^n}\ge1, \qquad\text{hence}\qquad \frac{n^n}{e^{,n-1}}\le n!. ]
Next define [ B_n=\frac{e^{,n-1}n!}{n^{n+1}}. ] Again (B_1=1), and [ \frac{B_{n+1}}{B_n} =e\frac{n^{n+1}}{(n+1)^{n+1}} =\frac{e}{(1+1/n)^{n+1}}. ] Using (e^{1/(n+1)}\le (n+1)/n), which is the second inequality with (k=n+1), gives [ e\le \left(\frac{n+1}{n}\right)^{n+1} =(1+1/n)^{n+1}. ] Consequently (B_{n+1}/B_n\le1), so (B_n\le B_1=1). Hence [ \frac{e^{,n-1}n!}{n^{n+1}}\le1, \qquad\text{and therefore}\qquad n!\le \frac{n^{n+1}}{e^{,n-1}}. ]
For the boundary case (n=1), both inequalities reduce to (1\le1!\le1), so equality holds at the initial value used above. Thus, for every integer (n\ge1), [ \boxed{\frac{n^n}{e^{,n-1}}\le n!\le \frac{n^{n+1}}{e^{,n-1}}}. ]
This completes the proof. ∎