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

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

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

• I see the fibonacci sequence with what is definable through the your method. (1) 1,2,3,5,8,... Commented Dec 9, 2016 at 12:43
• Which is always increasing. Am I right ??@KitterCatter Commented Dec 9, 2016 at 12:46
• Yeah. Though I think you are right to be uneasy about some of the terms not being well defined. Commented Dec 9, 2016 at 12:47
• Well, I agree....:P :P Commented Dec 9, 2016 at 12:49
• This question is about the same equation, but for real functions: Find all functions f such that $f(f(x))=f(x)+x$. Found using Approach0. Commented Jan 7, 2017 at 15:56

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.
• I didn't get:$|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 n))|$. I'm missing $-\alpha f(n)$. Commented Dec 9, 2016 at 13:13
• The occurrence of the golden ratio is natural in view of the recursive formula $$f^{\circ (k+2)}(n) = f^{\circ (k+1)}(n) + f^{\circ k}(n)$$ yet the construction is so simple and elegant. How did you come up with this? (+1) Commented Dec 9, 2016 at 13:16