Functional Equations: Olympiads

Aritro Pathak Although your approach is correct I will give a rigorous proof of our conjecture. We need to prove that

For $n=0,1,2,...$

$f(3^n)=2 \cdot 3^n$ and $f(2 \cdot 3^n)=3^{n+1}$

Proof: We will use induction. Notice that $f(1) \neq 1$ otherwise $3=f(f(1))=f(1)=1$ which is not true. Since $f (k)$ is a positive integer for all positive integers $k$ , we conclude that $f (1) > 1$ .Since $f (n + 1) > f (n), f$ is increasing. Thus $1 < f (1) < f ( f (1)) = 3$ or $f (1) = 2$ . Hence $f (2) = f ( f (1)) = 3$ .

Suppose that for some positive integer $n \geq 1$ ,

$f(3^n)=2 \cdot 3^n$ and $f(2 \cdot 3^n)=3^{n+1}$

$f(3^{n+1})=f(f(2 \cdot 3^n))=2 \cdot 3^{n+1}$

$f(2 \cdot 3^{n+1})=f(f(3^{n+1}))=3^{n+2}$

as desired. This completes the induction and hence the "guess" is proved.

There are $3^n-1$ integers which we call $'m'$ such that $3^n < m < 2 \cdot 3^n$ and there are $3^n-1$ integers $p$ such that

$f(3^n)=2 \cdot 3^n<p<3^{n+1}=f(2 \cdot 3^n)$

$f$ is increasing so $f(3^n+m)=2.3^n+m$ for $0 \leq m \leq 3^n$

Therefore $f(2 \cdot 3^n+m)=f(f(3^n+m))=3(3^n+m)$ for $0 \leq m \leq 3^n$

Hence $f(2015)=f(2 · 36 + 543)= 3(36 + 543)=\boxed{3816}$

I have written it very very cautiously still bring my attention towards mistakes,if any,thank you!!

It's easy to construct the values of the function for the initial integer values. Because the function has to be strictly increasing, this makes it routine . It's seen that $f(3^{k})=2 \times 3^{k}$ , for $k \geq 1$ and it increases by unity in each step until $f(2\times 3^{k})=3^{k+1}$ .

Similarly, from $f(2\times 3^{k})$ , till $f(3^{k+1})$ , the values increase by multiples of 3, till we get $f(3^{k+1})=2 \times 3^{k+1}$ .

Thus any value can be computed. 2015 lies between $3^{6}$ and $3^{7}$ ; and we get: $\boxed{f(2015)=3858}$