Find all $f:\mathbb{N} \to \mathbb{N}$ such that $f(f(n)) = 2n$

Question

Find all $f:\mathbb{N} \to \mathbb{N}$ such that $f(f(n)) = 2n\; \forall n \in \mathbb{N}$

If it was $f:\mathbb{R} \to \mathbb{R}$ then the solution was simply $f(n) = \sqrt{2}n$. But how to solve when $f : \mathbb{N} \to \mathbb{N}$ ?

Answer 1

There are many functions $f$ that work.

Here is an uncountable family of them:

Consider all the possible partitions of the odd integers into ordered pairs.

If you have the ordered pair $(a,b)$ then we define $f(b2^k)=a2^k$ and $f(a2^{k})=b2^{k+1}$.

We let $f(0)=0$.

This already gives us a bunch of extremely weird functions $f$, and of course, there are weirder ones.