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

Part A: $f(1)=2$.

First $f(1)$ cannot be $1$. Otherwise $3=f(f(1)) = f(1) = 1$.

So $f(1)$ is at least $2$. But $3 = f(f(1)) > f(2)$ because $f$ is increasing and $f(1)>2$.

Then $f(2)$ can only be $2$ or $1$. But $f(1)$ is at least $2$ and $f(1)<f(2)$. This is a contradiction. So $f(1)$ must be $2$.

Part B

Since $2 = f(1)$, then $f(2) = f(f(1)) = 3\cdot1 = 3$. Similarly $f(3) = f(f(2)) = 6$ and

$f(6) = f(f(3)) = 9$.

Since f is strictly increasing, then $f(4)$ and $f(5)$ has to be $7$ and $8$.

Part C

Claim: $f(3^n) = 2\cdot 3^n $

Why? Let $f(n) = x$. Then $f(f(n)) = f(x)$.

So $3n = f(x)$. And $f(3n) = f(f(x)) = 3x = 3f(n)$. So iteration follows:

$$f(3^n) = 3f(3^{n-1}) = \ldots = 3^n\cdot f(1) = 2\cdot3^n$$

From this result,

$$f(2\cdot3^n) = f(f(3^n)) = 3\cdot3^n$$

Now for $x\in[3^n, 2\cdot3^n]$, $f(x)\in[2\cdot3^n, 3\cdot3^n]$. Both $x$ and $f(x)$ have exactly $3^n$ values. Note that $f(x)$ has to be positive integers and strictly increasing. Thus if $x$ increases by $1$, $f(x)$ has to increase by $1$ too. So

$$ f(3^n + m) = 2\cdot3^n + m ; m \in [0,3^n]$$

Part D

Claim:$ f(2\cdot3^n + m) = 3(3^n + m) ; m \in [0,3^n]$.

Why? From Part C, $f(2\cdot3^n) = 3\cdot3^n$ and $f(3\cdot3^n) = 2\cdot3^{n+1}$

For any $x\in[2\cdot3^n, 3\cdot3^n]$, based on result of C, there exists a z such that $x = f(z) = 2\cdot 3^n + m$ where $z = 3^n + m$, and $m\in[0,3^n]$. Hence, $f(x) = f(f(z)) = 3z$, i.e.

$$ f(2\cdot 3^n + m) = 3\cdot(3^n + m) ; m \in [0,3^n]$$

Part E

$f(2001) = f(2\cdot3^6 + 543) = 3(3^6 + 543) = 3\cdot(729+543) = 3816$.

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$).