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

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

• There needs to be more restraints; is there a condition that $f(n)$ is an increasing function? – S.C.B. Jan 24 '17 at 15:42
• There are other functions $f:\mathbb R\to\mathbb R$ than $f(x)=\sqrt2x$, such that $f(f(x))=2x$ identically. – Did Jan 24 '17 at 15:45
• @S.C.B. no... There is no condition like that ... But it said the function must be true for all $n \in \mathbb{N}$ – 0123456789101112 Jan 24 '17 at 15:45
• @Did I would like to know the solutions for $f:\mathbb{R} \to \mathbb{R}$ also. – 0123456789101112 Jan 24 '17 at 15:47
• For an example showing that to give every solution is probably hopeless, consider $$f(2^n(4k+1))=2^n(4k+3)\qquad f(2^n(4k+3))=4^n(4k+1)$$ for every nonnegative $(n,k)$. This defines $f$ on $\mathbb N$ such that $f(f(n))=2n$ for every $n$. – Did Jan 24 '17 at 15:57

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.

• Is $0 \in \mathbb{N}$ ? – Rezwan Arefin Jan 24 '17 at 15:59
• Well, if it isn't just omit the second to last line and we're still good to go. – Yorch Jan 24 '17 at 16:00
• Nice! Is there a quick way to see that all possibles partitions constitute an uncountable family? – PAM Jan 24 '17 at 16:02
• @PAM Since the pairs are "ordered", it is clear that they are uncountable, since we can give an uncountable number of orientations to each partition. But even without this it is true that the number of unoriented partitions is uncountable.To see this it suffices to restrict our attention to the partitions that always pair up elements that are $1\bmod 4$ with elements that are $3\bmod 4$. The number of such partitions is clearly equal to the number of bijections from $\mathbb N$ to $\mathbb N$, which is known to be uncountable. – Yorch Jan 24 '17 at 16:08
• @PAM one way to see the number of bijections on an infinite set $A$ is larger than $A$ itself is to notice that for every subset $B$ not of the form $B\setminus \{x\}$ we can find a permutation such that the set of fixed elements of the permutation is $B$, and then using Cantor's theorem. – Yorch Jan 24 '17 at 16:16