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

We prove the stronger bound $T(n)\le 2n^2$ for every $n\ge 1$ by strong induction. The initial case is $T(1)=1\le 2$. For $n\ge 2$, put $m=\lfloor n/2\rfloor$. Then $1\le m<n$, so the induction hypothesis and the defining recurrence relation giveThusThe recurrence relation must be read as applying for $n\ge 2$; applying it at $n=1$ would invoke $T(0)$ outside the printed domain. No value of $T(0)$ is needed.