Is there a function $f: \mathbb{N}\rightarrow\mathbb{N}$ (strictly increasing) , such that the following is always true:
$$f(f(f(n))) = n + 2f(n)?$$
This is a homework problem from a contest math course I desperately need help with. I tried, but haven't made any significant progress.
Thank you in advance!
Just sketch: first of all, I'd focus on linear estimations $f(n)\approx g(x)$, where: $$g(x) = \alpha x,\qquad \alpha\ge 1,$$ from where $$\alpha^3 = 1+2\alpha,$$ therefore $$\alpha_1=-1, \\ \alpha_2=1 - \varphi, \\ \alpha_3 = \varphi,$$ where $\varphi=...$ (?)
Since $f$ is increasing function, we choose $\alpha=\varphi>1$.
Since $f$ is $\mathbb{N}\rightarrow\mathbb{N}$, $-$ there is reason to focus on functions like $$f(n)=round(\varphi n),$$ or something based on Fibonacci sequence: $$ f(\color{blue}{1})=\color{red}{2};\\ f(\color{blue}{2})=\color{red}{3};\\ f(\color{blue}{3})=\color{red}{5};\\ f(4)=6;\\ f(\color{blue}{5})=\color{red}{8};\\ f(6)=10;\\ f(7)=11;\\ f(\color{blue}{8})=\color{red}{13};\\ f(9)=15;\\ f(10)=16;\\ f(11)=18;\\ \ldots $$
Check first values:
$fff(1)=ff(2)=f(3)=5=1+2f(1)$;
$fff(2)=ff(3)=f(5)=8=2+2f(2)$;
$fff(3)=ff(5)=f(8)=13=3+2f(3);$
$fff(4)=ff(6)=f(10)=16=4+2f(4);$
$fff(5)=ff(8)=f(13)=21=5+2f(5).$
I'm not sure whether it will work further;) but you can try to derive/construct/prove something from here.