6

Came across this problem a little while ago but can't seem to get beyond a certain point.

Let $f:\mathbb{N} \rightarrow \mathbb{N}$ such that $f(n+1)>f(n)$ and $$f(f(n))=3n$$ for all $n$. Evaluate $f(2001)$.

I think induction might be the best way to approach this, but I can't even work out a good lemma to start with.

This question is very different to the "duplicate". The other one, though sharing the same equation, is simpler requiring only to calculate $f(10)$, no lemma or induction required.

user26857
  • 52,094
John Marty
  • 3,650
  • Related: http://math.stackexchange.com/questions/337208/function-olympiad-problem-define-fn-such-that-fn-is-a-positive-integer – Aryabhata May 09 '13 at 04:31

1 Answers1

8

Usually the way to start is pick some good values for the variables.
Assuming $0 \in \Bbb N$ (it doesn't really matter), we have $f(f(0))=0$, and since $f$ is strictly monotonic it gives $f(0)=0$.
Then we know that $f(f(1))=3$, so $f(1)$ must be $2$-if it were $1$ we would have $f(f(1))=1$ and $f(2)=3$
Now we have $f(f(2))=f(3)=6$, $f(f(3))=f(6)=9$ and that says $f(4)=7, f(5)=8$
We continue this way, getting $$\begin {array} {r | r} n & f(n)\\ \hline 0&0\\1&2\\2&3\\3&6\\4&7\\5&8\\6&9\\7&12\\8&15\\9&18\\10&19\\11&20\\12&21\\13&22\\14&23\\15&24\\16&25\\17&26\\18&27\\19&30\end {array}$$ Our hypothesis is that $f(3^n)=2\cdot 3^n$ then the values increase by $1$ until $f(2\cdot 3^n)=3^{n+1}$ then the values increase by $3$ until $f(3^{n+1})=2\cdot 3^{n+1}$
You are right that this can be proven by induction, but I leave it to you.
Then, since $2001=2\cdot3^6+543, f(2001)=3^7+3\cdot 543=3816$

Peter Taylor
  • 13,425
Ross Millikan
  • 374,822
  • I don't understand your last sentence. Could you enlighten me? – Julien May 09 '13 at 03:59
  • @julien: I looked whether $2001$ was between a $3^n$ and $2\cdot 3^n$ or between $2\cdot 3^n$ and $3^{n+1}$. I found the latter with $n=6$. Then I plugged in to my hypothesis, which says for $2 \cdot 3^n \le m \lt 3^{n+1}, f(m)=3^{n+1}+3(m-2\cdot 3^n)$ – Ross Millikan May 09 '13 at 04:04