Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 3 / f / ii / Solution

We prove the stronger explicit bound $n!\le n^n/2^{n-1}$ by mathematical induction. The case $n=1$ is equality. The binomial theorem gives $(1+1/n{)}^n\ge 1+n/n=2$, so $(n+1{)}^n\ge 2n^n$. Consequently the induction hypothesis yieldsTherefore $n!=O(n^n/2^n)$, with constant $2$ and threshold $1$.

The second bound is asymptotically tighter. Using $n\le 2^n$,Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.