Finding existence of $ f : N → N $ with the following properties: $f(1) = 2$ and $f(f(n)) = f(n)+n (n ∈ N).$

Question

I have got a question related to functional equations which is as follow:

Let $N =$ {${1,2,3,...}$}. Determine whether there exists a strictly increasing function $ f : N → N $ with the following properties:

$f(1) = 2$ and $f(f(n)) = f(n)+n$ where $(n ∈ N)$.

I tried applying the method which I apply to every question of such kind.

Put $n=1$ and then $f(f(1)) = f(1)+1\implies f(2)=3$

Put $n=2$ and then $f(f(2)) = f(2)+2\implies f(3)=5$

Now, if I put $n=3$ I will get $f(f(3)) = f(3)+3\implies f(5)=8$.

There are two problems now.

$1.$ I don't see any pattern.

$2.$ If I continue this way. I will miss $n=4,6,7......$

What to do now. Please help, any suggestion is heartily welcome.

Edit: This is IMO1993 Contest Problem 5 (2nd problem on 2nd day).

Answer 1

Notice that for $\displaystyle\alpha = \frac{1+\sqrt{5}}{2}$, $\displaystyle\alpha^{2}n=\alpha n+n$ for all $n \in \mathbb N$. We shall show that $\displaystyle f(n)= \lfloor(\alpha n+\frac{1}{2})\rfloor$ satisfies the requirements.

---

Observe that $f$ is strictly increasing and $f(1)=2$. By the definition of $f$, $|f(n)-\alpha n| \leq \frac{1}{2}$ and $f(f(n))-f(n)-n$ is an integer. On the other hand, $$|f(f(n))-f(n)-n| =|f(f(n)) -f(n)-\alpha^{2}n +\alpha n|$$ $$=|f(f(n))-\alpha f(n) +\alpha f(n) -\alpha^{2}n -f(n) +\alpha n|$$ $$=|(\alpha -1)(f(n)-\alpha n) +(f(f(n))-\alpha f(n))|$$ $$\leq (\alpha -1)|f(n)-\alpha n| + |f(f(n))-\alpha f(n)|$$ $$\leq \frac{1}{2}(\alpha -1) + \frac{1}{2} = \frac{1}{2}\alpha <1$$ which implies that $$f(f(n))-f(n)-n=0.$$ Hope it helps.