Asian Pacific Mathematics Olympiad

(a) Let
$$L_1:=\{2 k: k>0\}, \quad E_1:=\{0\} \cup\{4 k+1: k \geq 0\}, \quad \text{ and } \quad G_1:=\{4 k+3: k \geq 0\} .$$
We will show that $L_1=L$, $E_1=E$, and $G_1=G$. It suffices to verify that $L_1 \subseteq L$, $E_1 \subseteq E$, and $G_1 \subseteq G$ because $L_1$, $E_1$, and $G_1$ are mutually disjoint and $L_1 \cup E_1 \cup G_1=\mathbb{N}_0$.

Firstly, if $k>0$, then $f(2 k)-f(2 k+1)=-k<0$ and therefore $L_1 \subseteq L$.

Secondly, $f(0)=0$ and
$$\begin{aligned} & f(4 k+1)=2 k+2 f(2 k)=2 k+4 f(k) \\ & f(4 k+2)=2 f(2 k+1)=2(k+2 f(k))=2 k+4 f(k) \end{aligned}$$
for all $k \geq 0$. Thus, $E_1 \subseteq E$.

Lastly, in order to prove $G_1 \subset G$, we claim that $f(n+1)-f(n) \leq n$ for all $n$. (In fact, one can prove a stronger inequality: $f(n+1)-f(n) \leq n / 2$.) This is clearly true for even $n$ from the definition since for $n=2 t$,
$$f(2 t+1)-f(2 t)=t \leq n$$
If $n=2 t+1$ is odd, then (assuming inductively that the result holds for all nonnegative $m<n$ ), we have
$$\begin{aligned} f(n+1)-f(n) & =f(2 t+2)-f(2 t+1)=2 f(t+1)-t-2 f(t) \\ & =2(f(t+1)-f(t))-t \leq 2 t-t=t<n . \end{aligned}$$
For all $k \geq 0$,
$$\begin{aligned} & f(4 k+4)-f(4 k+3)=f(2(2 k+2))-f(2(2 k+1)+1) \\ & =4 f(k+1)-(2 k+1+2 f(2 k+1))=4 f(k+1)-(2 k+1+2 k+4 f(k)) \\ & =4(f(k+1)-f(k))-(4 k+1) \leq 4 k-(4 k+1)<0 \end{aligned}$$
This proves $G_1 \subseteq G$.

(b) Note that $a_0=a_1=f(1)=0$. Let $k \geq 2$ and let $N_k=\left\{0,1,2, \ldots, 2^k\right\}$. First we claim that the maximum $a_k$ occurs at the largest number in $G \cap N_k$, that is, $a_k=f\left(2^k-1\right)$. We use mathematical induction on $k$ to prove the claim. Note that $a_2=f(3)=f\left(2^2-1\right)$.

Now let $k \geq 3$. For every even number $2 t$ with $2^{k-1}+1<2 t \leq 2^k$,
$$\begin{equation*} f(2 t)=2 f(t) \leq 2 a_{k-1}=2 f\left(2^{k-1}-1\right) \tag{$\dagger$} \end{equation*}$$
by induction hypothesis. For every odd number $2 t+1$ with $2^{k-1}+1 \leq 2 t+1<2^k$,
$$\begin{align*} f(2 t+1) & =t+2 f(t) \leq 2^{k-1}-1+2 f(t) \\ & \leq 2^{k-1}-1+2 a_{k-1}=2^{k-1}-1+2 f\left(2^{k-1}-1\right) \tag{$\ddagger$} \end{align*}$$
again by induction hypothesis. Combining ($\dagger$), ($\ddagger$) and
$$f\left(2^k-1\right)=f\left(2\left(2^{k-1}-1\right)+1\right)=2^{k-1}-1+2 f\left(2^{k-1}-1\right),$$
we may conclude that $a_k=f\left(2^k-1\right)$ as desired.

Furthermore, we obtain
$$a_k=2 a_{k-1}+2^{k-1}-1$$
for all $k \geq 3$. Note that this recursive formula for $a_k$ also holds for $k \geq 0,1$ and 2. Unwinding this recursive formula, we finally get
$$\begin{aligned} a_k & =2 a_{k-1}+2^{k-1}-1=2\left(2 a_{k-2}+2^{k-2}-1\right)+2^{k-1}-1 \\ & =2^2 a_{k-2}+2 \cdot 2^{k-1}-2-1=2^2\left(2 a_{k-3}+2^{k-3}-1\right)+2 \cdot 2^{k-1}-2-1 \\ & =2^3 a_{k-3}+3 \cdot 2^{k-1}-2^2-2-1 \\ & \vdots \\ & =2^k a_0+k 2^{k-1}-2^{k-1}-2^{k-2}-\ldots-2-1 \\ & =k 2^{k-1}-2^k+1 \quad \text{ for all } k \geq 0 \end{aligned}$$