Let $f:\mathbb N\to \mathbb N$ be a strictly increasing function such that $f\bigl(f(n)\bigr)= 3n\ \forall\ n\in \mathbb N$
Find the value of $f(2001).$
Now I tried to solve this by myself but I'm stuck somewhere in the middle of my solution. Please help me with my solution. Also my solution is a bit long as I'm writing almost every observation I made, so please be kind enough to bear with me.
My Approach:
We know that $f$ is strictly increasing.
Suppose for some $n_1$ and $n_2$, we have $f(n_1)=f(n_2)$. Thus $f\bigl(f(n_1)\bigr)=f\bigl(f(n_2)\bigr)\implies 3n_1=3n_2$ hence $n_1=n_2$.
(I just realized that his step was actually not required.)
$\therefore$ $f$ is an injective strictly increasing function.
Suppose for some $n\in \mathbb N$, we have $f(n)\leq n$, then $f\bigl(f(n))\leq f(n)\leq n$ as $f$ is strictly increasing.
This gives us $3n\leq n$ which isn't true for any $n\in \mathbb N$.
$\therefore f(n)>n\ \forall\ n\in \mathbb N $
Now suppose $f(1)=l>1$. Thus $f\bigl(f(1)\bigr)=3=f(l)>f(1)=l\implies 1<l<3$ and since $l\in \mathbb N$, we know that $f(1)=2$.
This means that $f\bigl(f(1)\bigr)=f(2)=3$ and $f\bigl(f(2)\bigr)=f(3)=6$ and so on.
A few such values are:
$f(1)=2$
$f(2)=3$
$f(3)=6$
$f(6)=9$
$f(9)=18$
$f(18)=27$
$f(27)=54$
$f(54)=81$
Now here a pattern can be observed.
Claim: $f(3^n)=2\cdot3^n$
Proof: Suppose the above claim is true. Then $f\bigl(f(3^n)\bigr)=f(2\cdot3^n)=3^{n+1}$. Now $f\left(3^{n+1}\right)=f\bigl(f(2\cdot3^n)\bigr)=2\cdot3^n\cdot3=2\cdot3^{n+1}$
$\therefore$ $f(3^n)=2\cdot3^n$ and $f(2\cdot3^n)=3^{n+1}$
One more thing can be observed here that if $3^n<k<2\cdot3^n$, then $2\cdot3^n<f(k)<3^{n+1}$ and since there are exactly $3^n$ permitted values for both $k$ and $f(k)$ and $f$ is strictly increasing, the unique function satisfying the given condition can easily be found.
But unfortunately $2\cdot3^6<2001<3^7$, thus a unique function cannot be found using the observation stated above.
Now this is where I am stuck. Firstly, is this question solvable using my approach? If yes, then what should I add to my approach in order to reach the solution? Please help.
THANKS
Best Answer
$f(f(7))=21$, but we have $f(12)=21$ from the "exactly $3^n$ permitted values" point, so $f(7)=12$. In the same way we can show $f(8)=15,f(19)=30$ and so on. In general $$f(3^n)=2\cdot3^n$$ $$f(2\cdot3^n)=3\cdot3^n$$ $$f(3^n+k)=2\cdot3^n+k,0\le k\le3^n$$ $$f(2\cdot3^n+k)=3\cdot3^n+\mathbf{3k},\ 0\le k\le 3^n$$ Thus $$f(2001)=f(2\cdot3^6+543)=3\cdot3^6+3\cdot543=3816$$ $f$ is OEIS A003605. The same question but asking for $f(1992)$ was problem 5 of BMO 1992.