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

Use natural logarithms; the same argument works for any fixed base greater than

1

lo g lo g x

is increasing for

x > 1

, since its derivative is

1/ (x lo g x) > 0

. With natural logs the sole negative summand is at

i = 2

. Put

C_{0} = ∣ lo g lo g 2∣

For all sufficiently large

n

with

lo g lo g n \geq 1

, monotonicity and the triangle inequality give

∣ \sum_{i = 2}^{n} lo g lo g i ∣ \leq C_{0} + \sum_{i = 3}^{n} lo g lo g i \leq C_{0} + n lo g lo g n \leq (1 + C_{0}) n lo g lo g n .

These are fixed constants and an eventual bound, proving

i = 2 \sum n lo g lo g i = O (n lo g lo g n) .

For another fixed logarithm base there are still only finitely many negative initial terms, which are absorbed in

C_{0}

 New to topics? Read the docs here!