5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – draks ... Jul 23 '12 at 16:01
  • 2
    $\begingroup$ 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. $\endgroup$ – Micah Jul 23 '12 at 16:39
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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