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 / e / ii / Solution

Multiplying the recurrence relation by $n$ removes the average:For $n\ge 2$, subtract the same identity at $n-1$:Rearranging gives $T(n)=T(n-1)+2-1/n$. This also holds at $n=1$, because the original recurrence relation gives $T(1)=1$ and $T(0)=0$. Summing the differences therefore yieldsHere $H_n$ is a harmonic number. Since $H_n\le n$, we have $n\le T(n)\le 2n$ for $n\ge 1$, also establishing $\Theta (n)$ in big theta notation.