Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability (resit) / 3 / d

Use natural logarithms; the same argument works for any fixed base greater than $1$. The function $\log \log x$ is increasing for $x>1$, since its derivative is $1/(x\log x)>0$. With natural logs the sole negative summand is at $i=2$. Put $C_0=|\log \log 2|$.

For all sufficiently large $n$ with $\log \log n\ge 1$, monotonicity and the triangle inequality giveThese are fixed constants and an eventual bound, provingFor another fixed logarithm base there are still only finitely many negative initial terms, which are absorbed in $C_0$.

For natural logarithms and sufficiently large $n$, take the logarithm of the positive expression:Set $t=\log \log n$. Then $\log n=e^t$. The exponential function grows faster than $t^2$: for example, its power series gives $e^t\ge t^3/6$ for $t>0$, so $t^2/e^t\le 6/t\to 0$. In particular, eventually $(\log \log n{)}^2\le \log n$. Exponentiating yieldsFor logarithms to a fixed base $b>1$, the natural logarithm of the left side is $(\log \log n-\log \log b{)}^2/\log b$, still smaller than $\log n$ eventually. The big O notation conclusion is therefore independent of that base choice.