# Functional Equation with Value

If $f$ is a strictly increasing function from the naturals to the naturals, and $f(f(x))=3x$, what are all values of $f(2012)$? I have only proven that $f(3x)=3f(x)$ but that get's nowhere :(

• What if you wait for one more year? Can you use your partial result then...btw: Can you show us how you have proven it? – draks ... Jul 23 '12 at 16:01
• I suggest that you start by looking at $f(x)$ for small values of $x$; look for a pattern when $x$ is written in base 3. – Micah Jul 23 '12 at 16:39

Proposition. $f(1) = 2$, $f(2) = 3$.

Proof. $f(1)$ cannot be $1$ otherwise we would have $$3 = f(f(1)) = f(1) = 1$$ So $f(1) > 1$ and since $f$ is strictly increasing, $f(x) > x$ for each $x$.
Being $3 = f(f(1)) > f(1)$, the only remaining possibility is $f(1) = 2$.
Finally, $f(2) = f(f(1)) = 3$. $\blacksquare$

Proposition. $f(3^n x) = 3^n f(x)$.

Proof. This is a direct consequence of the relation $$f(3x) = f(f(f(x))) = 3f(x)\; \blacksquare$$

Proposition. If $3^n < x \leq 2\cdot 3^n$ then $f(x) = 3^n + x$.

Proof. It's sufficient to note that there are exactly $3^n$ numbers between $3^n$ and $2\cdot 3^n$, and exactly $3^n$ numbers between $$f(3^n) = 3^nf(1)= 2\cdot 3^n$$ and $$f(2\cdot 3^n) = 3^nf(2) = 3^{n +1} \; \blacksquare$$

Proposition. If $2\cdot 3^n < x \leq 3^{n + 1}$ then $f(x) = 3x - 3^{n + 1}$.

Proof. Since $3^n < x - 3^n \leq 2\cdot 3^n$, the previous proposition implies $f(x -3^n) = x$ and therefore $$f(x) = f(f(x - 3^n)) = 3x - 3^{n + 1} \; \blacksquare$$

Being $2\cdot 3^6 < 2012 \leq 3^7$, from last proposition we can conclude $$f(2012) = 3\cdot 2012 - 3^7 = 3849$$