Find the functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $f(2 n)=2 f(n)$ and $f(2 n+1)=2 f(n)+1$ for all $n \in \mathbb{N}$.
Let $f$ be a potential solution to the problem. From the given relations, it is clear that if we know the initial values of $f$, we can deduce all the values of $f$ step by step.

We start by choosing $n=0$, and we get $f(0)=2 f(0)$, hence $f(0)=0$.

For $n=1$, we have $f(1)=f(2+1)=2 f(0)+1=1$.

For $n=2$, we have $f(2)=f(2)=2 f(1)=2$.

For $n=3$, we have $f(3)=f(2+1)=2 f(1)+1=3 \ldots$

It seems that $f(n)=n$ for all $n$. This is true for $n=0,1,2,3$. Fix an $n>1$ and assume that $f(k)=k$ for all $k \leq n$. We will prove that $f(n+1)=n+1$.

- 1st case: if $n+1$ is even. Then $n+1=2a$ for some integer $a$ such that $0 \leq a \leq n$, and thus $f(a)=a$. Consequently, $f(n+1)=f(2a)=2 f(a)=2a=n+1$.
- 2nd case: if $n+1$ is odd. Then, by construction, $f(n+1)=2 f(n / 2)+1=n+1$.

Therefore, in all cases, $f(n+1)=n+1$. Finally, step by step, we have $f(n)=n$ for all $n$. Conversely, it is clear that such a function is indeed a solution to the problem, and there is only one solution, which is the function $n \mapsto n$.