 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2022/discrete-mathematics-continuous-mathematics-and-probability-resit/2/c/iv/solution

True for every fixed $k \geq 0$ . Extract

e^{n}

from inside the logarithm:

lo g (e^{n} + n^{k}) - n = lo g (1 + n^{k} e^{- n}) .

Choose an integer

m > k

. The nonnegative terms of the exponential series give

e^{n} \geq n^{m} / m!

for

n > 0

, whence

0 \leq n^{k} e^{- n} \leq m! n^{k - m} ⟶ 0.

Since

0 \leq lo g (1 + u) \leq u

for

u \geq 0

, the displayed expression tends to zero and is therefore

O (1)

. The constant and cutoff may depend on the fixed

k

; no uniform assertion over unbounded

k

is being made.

 New to topics? Read the docs here!