<s>[INST] If $f: \Bbb{N} \to \Bbb{N}$ is strictly increasing and $f(f(n))=3n$, find $f(2001)$. 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)$.

 [/INST] 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$.
</s>