Азиатско-Тихоокеанская олимпиада по математике 2008 года | Казахстанские олимпиады

Рассмотрим функцию $f : \mathbb{N}_0 \to \mathbb{N}_0$, где $\mathbb{N}_0$ — множество неотрицательных целых чисел, которая определяет следующие условия:
(i) $f(0) = 0$,
(ii) $f(2n) = 2f(n)$ и
(iii) $f(2n + 1) = n + 2f(n)$, для всех $n \geq 0$.
(a) Определите три множества $L$, $E$, $G$ такие, что $L= \{n| f(n) < f(n + 1)\}$, $E= \{n | f(n) = f(n + 1)\}$ и $G= \{ n|f(n) > f(n + 1)\}$.
(b) Для каждого $k \geq 0$, найдите общую формулу для $a_k$ относительно $k$, для которой $a_k = \max \{f(n): 0 \leq n \leq 2^k\}$.