# Integer functional equation $f(f(f(n)))=f(n+1)+1$

Can you find all functions $f:\mathbb N\rightarrow\mathbb N$ satisfying the functional equation $$f(f(f(n)))=f(n+1)+1$$

• Are you saying that the equation only needs to be satisfied for $n>0$, but $f$ can take any values in $\mathbb N$, positive or negative or 0? – Alex Meiburg Apr 7 '15 at 21:38
• I edited your question - please check if my edit is correct. – String Apr 7 '15 at 21:49
• If you assume $f(n)$ is polynomial, then you can show that $f(n)=n+1$. In fact, you can rule out any function such that $f(n)\to \infty$ that doesn't do so linearly. – abnry Apr 7 '15 at 21:50
• There is a solution here: math.stackexchange.com/questions/1122390/… – CIJ Apr 7 '15 at 21:56

The set of valid functions is given by $$f(n) = \begin{cases} n+1 & n \text{ even} \\ n+5 & n \equiv 1 \pmod 4 \\ n-3 & n \equiv 3 \pmod 4. \end{cases}$$ and $$f(n)=n+1$$. Solutions can be found here and the official solution can be found here (this is a download link).