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

Prove the explicit bound $n!\le 2^{n^2}$ by mathematical induction. At $n=1$, $1\le 2$. For the step, note that $n+1\le 2^n$ for $n\ge 1$: this auxiliary inequality has base $2=2$ and follows at the next index from $n+2\le 2(n+1)$. Hence, using the induction hypothesis,Thus $n!=O((2^n{)}^n)$, with constant $1$ and threshold $1$ in big O notation.

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.