APMO 2008 Problem 4

Consider the function $f: \mathbb{N}_{0} \rightarrow \mathbb{N}_{0}$, where $\mathbb{N}_{0}$ is the set of all non-negative integers, defined by the following conditions: (i) $f(0)=0$, (ii) $f(2 n)=2 f(n)$ and (iii) $f(2 n+1)=n+2 f(n)$ for all $n \geq 0$. (a) Determine the three sets $L:=\{n \mid f(n)<f(n+1)\}, E:=\{n \mid f(n)=f(n+1)\}$, and $G:=\{n \mid f(n)>f(n+1)\}$. (b) For each $k \geq 0$, find a formula for $a_{k}:=\max \left\{f(n): 0 \leq n \leq 2^{k}\right\}$ in terms of $k$.