Let $f:\mathbb N\to \mathbb N\;$ be a strictly increasing function s.t. $\;f\bigl(f(n)\bigr)=3n$ for all $n$. Find $f(2001)$ via a specific approach

Question

Let $f:\mathbb N\to \mathbb N\;$ be a strictly increasing function such that $\;f\bigl(f(n)\bigr)=3n\;$, for all natural numbers $n$. Find $f(2001)$.

Approach I want to follow:

Replace $n$ by $f(n)$ in $\;f\bigl(f(n)\bigr)=3n,\;$ for $m$ times. Therefore $$\underbrace{f\circ f\circ f\circ \dots\circ f}_\text{m+2 times}(n)=3\cdot \underbrace{f\circ f\circ f\circ \dots\circ f}_\text{m times}(n).\tag 1\label 1$$

Let $\;a_0=n\;$ for some fixed $\;n\;$ and $\; a_{m+1}=f(a_m)\;$ $\forall \; m\ge 0$.

From Equation \eqref{1} $$a_{m+2}=3\cdot a_{m}.$$ Its characteristic equation is $$x^{m+2}-3\cdot x^m=0, \;x\ne0$$ or $$x^2-3=0$$ $$\implies x=\pm \sqrt3.$$ $$\implies a_m=A(\sqrt{3})^m\;+\;B(-\sqrt{3})^m\;\forall \; m\ge 0.$$

And $A$ must be greater than $B$ otherwise $a_{m}$ will tend to $-\infty$ when $m$ is odd.

Now I am stuck. How can I proceed further using this method?

Or

We can't solve this problem using my method?

I know other methods to solve this problem.

This problem is same as "https://math.stackexchange.com/questions/1410635/if-f-bbbn-to-bbbn-is-strictly-increasing-and-ffn-3n-find-f200", but with a different method.

Answer 1

Your method does not seem to be promising. I try to explain myself by examining what information one can find by looking at the sequences you defined. (I will assume that by $ \mathbb N $ you mean the set of positive integers, which does not include $ 0 $.)

First, let's find out what the values of $ A $ and $ B $ must be. As $ a _ 0 = n $ and $ a _ 1 = f ( n ) $, you have the equations $ A + B = n $ and $ ( A - B ) \sqrt 3 = f ( n ) $, and consequently $ A = \frac 1 2 \left ( n + \frac { f ( n ) } { \sqrt 3 } \right ) $ and $ B = \frac 1 2 \left ( n - \frac { f ( n ) } { \sqrt 3 } \right ) $. This lets us rewrite the expression for $ a _ m $ as $$ a _ m = \frac { \sqrt 3 ^ m } 2 \left ( n \bigl ( 1 + ( - 1 ) ^ m \bigr ) + \frac { f ( n ) } { \sqrt 3 } \bigl ( 1 + ( - 1 ) ^ { m - 1 } \bigr ) \right ) = \begin {cases} n \cdot 3 ^ k & m = 2 k \text ; \\ f ( n ) \cdot 3 ^ k & m = 2 k + 1 \text . \end {cases} \tag {*} \label 0 $$

Next, let's derive some simple properties of $ f $ from the given assumptions. It's straightforward to prove that every strictly increasing function from $ \mathbb N $ to $ \mathbb N $ is greater than or equal to the identity function at all point. In other words, by the assumption that $ f $ is strictly increasing, we get $ f ( n ) \ge n $ for all $ n \in \mathbb N $, using mathematical induction on $ n $. Taking the functional equation into account, we get the strict inequality $ f ( n ) > n $ for all $ n \in \mathbb N $: if $ f ( n ) = n $ then $ 3 n = f \bigl ( f ( n ) \bigr ) = f ( n ) = n $, a contradiction. Now that we have this, we can use the fact that $ f $ is strictly increasing to get $ f ( n ) < f \bigl ( f ( n ) \bigr ) $ from $ n < f ( n ) $ for all $ n \in \mathbb N $. Using the functional equation again, we end up with $ n < f ( n ) < 3 n $ for all $ n \in \mathbb N $.

Finally, let's see what information we can get from \eqref{0}. As we had $ a _ m $ defined as $ f ^ m ( n ) $ (where $ f ^ m $ is the $ m $-th iteration of $ f $), the expression given in \eqref{0} already implies $ f \bigl ( f ( n ) \bigr ) = 3 n $, the given functional equation. But aside from that, there's nothing to say; the fact that for any $ n \in \mathbb N $ the sequence $ ( a _ m ) _ { m = 0 } ^ \infty $ is of that specific form is in fact equivalent to the fact that the functional equation holds. Let's take into account that $ f $ is strictly increasing. One may be able to derive $ n < f ( n ) < 3 n $ from \eqref{0} (after proving $ f ( n ) \ge n $ separately), but I think that would be using too much machinery, as there is already a simpler argument for that, like the one in the previous paragraph. Now, note that $ n < f ( n ) < 3 n $ is in fact equivalent to the fact that $ ( a _ m ) _ { m = 0 } ^ \infty $ is strictly increasing.

Aside from the facts mentioned above, the sequence doesn't seem to have any significance. The problem is that the specific sequence $ ( a _ m ) _ { m = 0 } ^ \infty $ is defined for some fixed $ n $, and that information doesn't seem to help us directly relate the formula in \eqref{0} to the value of $ f $ at any other points not appearing in this chain. So, as far as I can see, your method does not work, in the sense that seemingly it is not a step towards finding any properties of $ f $ besides the simple ones mentioned above.

Answer 2

The key issue with your approach is that one piece of data isn't enough to solve a second-order linear recurrence relation. While your formula is correct — and as Mohsen's answer suggests, it can be written as $a_{2n}=3^na_0$ and $a_{2n+1}=3^na_1$, this isn't enough to find $a_n$ from just $a_{n-1}$ — e.g., $f(2001)$ from $2001$ — because your sequence has two parameters, $a_0$ and $a_1$. It's similar to looking at a Fibonacci-style sequence satisfying $F_n=F_{n-1}+F_{n-2}$ and asking 'given that $F_5=73$, what is $F_6$?'. With $F_5$ and $F_4$ known, finding $F_6$ is easy, but with only $F_5$ there are many possibilities for $F_6$. Therefore, some additional information has to come into play.