= Solution
We prove the stronger explicit bound $n!\leq n^n/2^{n-1}$ by <mathematical induction>. The case $n=1$ is equality. The <binomial theorem> gives $(1+1/n)^n\geq1+n/n=2$, so $(n+1)^n\geq2n^n$. Consequently the <induction hypothesis> yields
$$
(n+1)!\leq\frac{(n+1)n^n}{2^{n-1}}\leq\frac{(n+1)^{n+1}}{2^n}.
$$
Therefore \b[$n!=O(n^n/2^n)$], with constant $2$ and threshold $1$.
The second bound is \b[asymptotically tighter]. Using $n\leq2^n$,
$$
\frac{n^n/2^n}{2^{n^2}}=\left(\frac{n}{2^{n+1}}\right)^n\leq2^{-n}\longrightarrow0.
$$
Thus its bounding function is negligible relative to the first in <little o notation>; this compares the bounds without needing <Stirling's formula>.
Back to article page
