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

  • 1
    $\begingroup$ 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? $\endgroup$ – Alex Meiburg Apr 7 '15 at 21:38
  • $\begingroup$ I edited your question - please check if my edit is correct. $\endgroup$ – String Apr 7 '15 at 21:49
  • $\begingroup$ 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. $\endgroup$ – abnry Apr 7 '15 at 21:50
  • 4
    $\begingroup$ There is a solution here: math.stackexchange.com/questions/1122390/… $\endgroup$ – 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.