If $f: \Bbb{N} \to \Bbb{N}$ is strictly increasing and $f(f(n))=3n$, find $f(2001)$.

Question

I have this question which seems a little harder than I thought. It has been about an hour for me hitting aimless thoughts on this one. I can really use a hint here if some one knows how to tackle it.

Let $f: \Bbb{N} \to \Bbb{N}$ such that $f$ is strictly increasing and $f(f(n))=3n$ for all $n \in \Bbb{N}$. Find $f(2001)$.

Answer 1

This solution does not meet the condition that f be increasing. I will leave it here in the hopes that someone can build on it.

One possible $f(n)$ can be constructed as follows:

Let $2^\beta$ be the highest power of two that divides $n$, and then define $g:\mathbb{N}\to\mathbb{N}$ accordingly

$$g(n)=\beta\text{ where }2^\beta\mid n\text{ and }2^{\beta+1}\nmid n \tag{1}$$

Then let $f(n)=\begin{cases} 2n, & \mbox{if } g(n)\mbox{ is even} \\ \frac{3n}{2}, & \mbox{if } g(n)\mbox{ is odd} \end{cases} \tag{2}$

It is clear that if $g(n)=\beta$ then we have $g(f(n))=\beta\pm1$, so that $g(n)$ and $g(f(n))$ have opposite parity. Thus, if $f(n)$ falls into one case, then $f(f(n))$ falls into the other.

Closure. Also, $f(n)$ only falls into the second case if $g(n)$ is odd, which means that $n=2m$ for some $m\in\mathbb{N}$. So then $f(n)=\frac{3}{2}n=3m\in\mathbb{N}$ too. This shows that $f(n)\in\mathbb{N}$ for all $n$.

So we have the identity $$\begin{align} f(f(n)) &= 2\times\frac{3}{2}n &(\text{in some order}) \\ &= 3n \end{align}$$

Since $2001=2^0\cdot3\cdot23\cdot29$, we can compute that

$$\boxed{f(2001)=2\times2001=4002}$$

is one possible solution.

Answer 2

Hint. I would begin by constructing the function explicitly at the lower end. You may find that it is fairly well constrained by the fact of being strictly increasing. For instance, we know that $f(1) = 2$: It cannot be $1$, because then $f(f(1)) = f(1) = 1 \not= 3$, and it cannot be $3$, because then $f(f(1)) = f(3) > f(1) = 3$. Therefore $f(2) = 3$. Therefore $f(3) = 6$. Therefore $f(6) = 9$.

Now observe that $f(3)$ and $f(6)$ squeeze $f(4)$ and $f(5)$ to be $7$ and $8$, respectively. Then $f(7) = 12$ and $f(8) = 15$. From $f(6)$, we have $f(9) = 18$. From $f(7)$, we have $f(12) = 21$, and now $f(10)$ and $f(11)$ are squeezed by $f(9)$ and $f(12)$.

If you can identify the regularity with which such values are squeezed, you may be able to obtain $f(2001)$.

ETA: This regularity may be easier to see if you express the numbers in ternary (base $3$).