 Solution

ID: 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! \leq n^{n} / 2^{n - 1}

n = 1

is equality. The binomial theorem gives

(1 + 1/ n)^{n} \geq 1 + n / n = 2

, so

(n + 1)^{n} \geq 2 n^{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 $n! = O (n^{n} / 2^{n})$ , with constant

2

and threshold

1

The second bound is asymptotically tighter. Using

n \leq 2^{n}

\frac{n ^{n} / 2 ^{n}}{2 ^{n^{2}}} = (\frac{n}{2 ^{n + 1}})^{n} \leq 2^{- n} ⟶ 0.

Thus its bounding function is negligible relative to the first in little o notation; this compares the bounds without needing Stirling's formula.

 New to topics? Read the docs here!