6

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

String
  • 18,395
Vincent P
  • 61
  • 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 07 '15 at 21:38
  • 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 07 '15 at 21:50
  • 4
    There is a solution here:

    http://math.stackexchange.com/questions/1122390/olympiad-style-question-about-functions-satisfying-condition-fffn-fn1

     – CIJ Apr 07 '15 at 21:56

1 Answers1

1

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

user574848
  • 1,335