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)\}$.

(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$.
(a) Let

$$
L_{1}:=\{2 k: k>0\}, \quad E_{1}:=\{0\} \cup\{4 k+1: k \geq 0\}, \text { and } 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 E, 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 \text {. }
$$

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}$,

$$
f(2 t)=2 f(t) \leq 2 a_{k-1}=2 f\left(2^{k-1}-1\right)
$$

by induction hypothesis. For every odd number $2 t+1$ with $2^{k-1}+1 \leq 2 t+1<2^{k}$,

$$
\begin{aligned}
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)
\end{aligned}
$$

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}
$$