Not so easy functional equation

It is very easy to see that: $f(f(1))=3 \rightarrow f(1)=2$ Because, if f(1)=1 then f(1)=3 (this is a confusion). $f(f(1))=f(2)=3, f(f(2))=f(3)=6, f(f(3))=f(6)=9, \rightarrow f(4)=7, f(5)=8$ $f(f(4))=f(7)=12, f(f(5))=f(8)=15, f(f(6))=f(9)=18, f(f(7))=f(12)=21$ $\rightarrow f(10)=\boxed{19}$

We will prove via induction on all non-negative integers $n$ a claim $P_n$ that:

• For $3^n \leq x \leq 2 \cdot 3^n$ , we have $f(x)=x+3^n$
• For $2 \cdot 3^n \leq x \leq 3^{n+1}$ , we have $f(x)=3x-3^{n+1}$

First, we prove that $f(1)=2$ .

If $f(1)=1$ , we have $f(f(1))=1=3$ , a contradiction, hence $f(1)>1$ and with the condition $f(n+1)>f(n)$ , we have $f(n)>n$ for all positive integers $n$ .

If $f(1) \geq 3$ , we'd have $f(f(1)) \geq f(3) >3$ , also a contradiction. Hence we must have $f(1)=2$ . Also, we have $f(2)=f(f(1))=3$ and $f(3)=f(f(2))=6$ .

We note that we have our claim $P_n$ be true for $n=0$ , given our values of $f(1),f(2),f(3)$ . Now assume for some non-negative integer $k$ , we have $P_k$ be true, i.e. that:

• For $3^k \leq x \leq 2 \cdot 3^k$ , we have $f(x)=x+3^k$
• For $2 \cdot 3^k \leq x \leq 3^{k+1}$ , we have $f(x)=3x-3^{k+1}$

We then consider the claim $P_{k+1}$ :

For $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , consider the $x$ where $x=3y$ for some integer $3^k \leq y \leq 2 \cdot 3^k$ . We then have $x=f(f(y))=f(y+3^k)$ , and consequently $f(x)=f(f(y+3^k)))=3(y+3^k)=3y+3^{k+1}=x+3^{k+1}$ .

For $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , there also exist $x,x+1$ where $3y<x<x+1<3(y+1)$ for some $(3^k \leq y \leq 2 \cdot 3^k-1$ . We can infer that $x=3y+1,x+1=3y+2$ . Then using our results that $f(3y)=3y+3^{k+1},f(3y+3)=3y+3+3^{k+1}$ from just now, we have:

$3y+3^{k+1}=f(3y)<f(x)<f(x+1)<f(3y+3)=3y+3+3^{k+1}$

We thus have $f(x)=3y+1+3^{k+1}=x+3^{k+1},f(x+1)=3y+2+3^{k+1}=x+1+3^{k+1}$ , hence we have it that for all $3^{k+1} \leq x \leq 2 \cdot 3^{k+1}$ , we have $f(x)=x+3^{k+1}$

For $2 \cdot 3^{k+1} \leq x \leq 3^{k+2}$ , we note that $3^{k+1} \leq x-3^{k+1} \leq 2 \cdot 3^{k+1}$ and from our previous result we have $f(x-3^{k+1})=x-3^{k+1}+3^{k+1}=x$ . Consequently, we have $f(x)=f(f(x-3^{k+1}))=3x-3^{k+2}$ .

Thus we have proven that with $P_0$ being true and $P_k$ being true $\Rightarrow$ $P_{k+1}$ being true, we have proven our claim that $P_n$ is true for all non-negative integers n.

Using the above formula, we have $f(10)= 19$ .