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

Because $T$ is positive, the definition of big O notation becomesHere $C$ and $n_0$ are fixed independently of $n$.

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.

By modular arithmetic, $a_1-b_1=nu$ and $a_2-b_2=nv$ for some integers $u,v$. Adding givesSince $u+v$ is an integer, this proves

Using $a_i=b_i+n{u}_i$ with integers $u_i$,The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives

By Euclidean division, write $a=qn+r$ and $b=sn+t$, with integers $q,s$ and $0\le r,t<n$. The hypothesis is $a\equiv b(\mathrm{mod}n)$. Apply the addition rule from part (b)(i) with $-qn\equiv -sn\equiv 0(\mathrm{mod}n)$ to obtainTherefore $n\mid r-t$. But $-n<r-t<n$, and the only multiple of $n$ in that interval is zero. Henceso the two remainders agree.

The decimal expansion is $a={\sum }_{i=0}^m{a}_{i}10^i$. Since $10\equiv 1(\mathrm{mod}3)$, repeated use of the multiplication rule in part (b)(ii) gives $10^i\equiv 1(\mathrm{mod}3)$ for every $i\ge 0$. Repeated use of the addition rule in part (b)(i) now givesIf $3\mid a$, the left side is congruent to zero, whenceThis is the decimal digit-sum divisibility test for three, derived directly from modular arithmetic.

Set $k=\lfloor x\rfloor$. The definition of the floor function gives $k\le x<k+1$. Adding the integer $m$ yieldsSince $k+m$ is an integer, it is exactly the floor of $x+m$. Thus

Put $k=\lfloor y^{1/n}\rfloor$. Because $y>0$, $k$ is a nonnegative integer, andThe function $t\mapsto t^n$ is strictly increasing for $t\ge 0$, so $k^n\le y<(k+1{)}^n$. Both powers are integers. Taking the floor function therefore givesTaking nonnegative $n$th roots now gives $k\le \lfloor y{\rfloor }^{1/n}<k+1$. ConsequentlyThe argument also covers $0<y<1$, when both outer floors are zero.