Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 :(

share|improve this question
    
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
2  
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

1 Answer 1

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 $$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.