Let N={1,2,3,…}. Determine if there exists a strictly increasing function $f:N→N$ such that
$f(1)=2$
$f(f(n))=f(n)+n$ for all n."
Here is the solution I came up with
We can see $f(1)=2$
$f(2)=3$
$f(3)=5$
Basically if $a_n$ is the $(n+2)^{th}$ term in the Fibonacci sequence starting from 1,1,2,3,5..
then I claim
$f(a_n)=a_{n+1}$
This can easily be proved by induction as follows
Assume $f(a_n)=a_{n+1}$
Then $f(a_{n+1})=f(a_{n})+a_n=a_{n+2}$
Now clearly $a_{n+1}-a_n<a_{n+2}-a_{n+1}$
So all numbers between $a_n$ and $a_{n+1}$ can be assigned any arbitrary value between $a_{n+2}$ and $a_{n+1}$ in increasing order and hence many such functions may exist
I wanted to know if my solution is correct because it looks rather simple and this is an IMO problem
In the step "assigning arbitrary values" the condition $f(f(n))=f(n)+n$ may not hold.