Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Discrete mathematics, probability and continuous mathematics / 2 / d / Solution

First consider powers of four, with a fixed finite base value. For a mathematical induction hypothesis $x_{n/4}\le C(n/4{)}^2$, the recurrence relation givesprovided $C\ge 4/3$ and $C$ also covers the base value.

The allowed integer rounding needs a little more care. Suppose the recurrence relation is applied above fixed base cases, as usual; applying $x_1=4x_1+1$ with a ceiling would not define a positive sequence. For either rounding write $m=\lceil n/4\rceil$ or $m=\lfloor n/4\rfloor$. For $n\ge 6$,Choose $C\ge 16/7$ large enough to bound all finitely many positive-index base values below $6$. By strong induction,This argument starts at $n=6$, so the floor convention's index zero, if used in an earlier base calculation, is absorbed into those fixed initial values. Thus, for either convention with a well-defined finite base,