Q4 Matemática  (APMO 2008)

Considere a função $f:{\mathbb{N}}_0\to {\mathbb{N}}_0$, onde ${\mathbb{N}}_0$ é o conjunto de todos os inteiros não negativos, definidos pelas seguintes condições: $(i)$ $f(0)=0$; $(ii)$ $f(2n)=2f(n)$ e $(iii)$ $f(2n+1)=n+2f(n)$ para todo $n\ge 0$. $(a)$ Determine os três conjuntos $L=\{n|f(n)<f(n+1)\}$, $E=\{n|f(n)=f(n+1)\}$, e $G=\{n|f(n)>f(n+1)\}$. $(b)$ Para cada $k\ge 0$, encontre uma fórmula para $a_k=\max \{f(n):0\le n\le 2^k\}$ em termos de $k$.