 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/i/solution

Prove the explicit bound

n! \leq 2^{n^{2}}

n = 1

1 \leq 2

. For the step, note that

n + 1 \leq 2^{n}

for

n \geq 1

: this auxiliary inequality has base

2 = 2

and follows at the next index from

n + 2 \leq 2 (n + 1)

(n + 1)! \leq (n + 1) 2^{n^{2}} \leq 2^{n^{2} + n} \leq 2^{(n + 1)^{2}} .

Thus $n! = O ((2^{n})^{n})$ , with constant

1

and threshold

1

 New to topics? Read the docs here!