Hello, This is my solution .

The answer is $f(x)=x+1$ which clearly works. First note that if we prove that $f(x) \geq x+1$ we're done. It's because: Let $f(x)=x+1+g(x)$. then $f^n(x) = f(x)+n-1+g(f^{n-1}(x))+g(f^{n-2}(x))+...+g(f(x))$ So the problem condition would be: $-1 \leq g(y) + g(f^{f(y)-1}(x))+g(f^{f(y)-2}(x))+...+g(f(x)) \leq 0$ which means $g(y)=0$ since $g$ was non-negative. Now let's prove that $f(x) \geq x+1$ Lemma1. 1 is not in $im(f)$ proof. assume that $f(t)=1$ for some $t$. then putting $P(x,t)$ in the main relation we'd get that $t=1$ . now putting $P(1,y)$ where $y>1$ we'd arrive contradiction. Lemma 2. there's no $x$ st $f(x)=x$ Proof. assume $f(t)=t$. putting $P(t,y)$ where $y>1$ we'd get a contradiction. Now let's proof by induction on $n$ that $f(n) \geq n+1$. for $1,2$ we have the desired statement by lemmas. assume that $f(3)=2$ ; by lemmas we cannot have $f(3)= 1 or 3$. now put $y=3$ in the main relation : $2 \leq f^2(x)-f(x) \leq 3$. now but $f(x)$ instead of $x$ in the main relation and do it untill you get the relation : $2 \leq f^{f(2)}(x) - f^{f(2)-1}(x) \leq 3$ which is clearly possible since $f(2) \geq 3$. But in each step we're taking an $f$ from $x$ , we're making $f(x) , f^i(x)$ two steps further. This will contradicts $P(2,x)$ and we should've $f(3) \geq 4$ Actually you can do similar stuff as this case , in the case $f(m)=n < m$ where $m$ is the first number that $f(m)<m$ ; that is writing $P(m,x)$ and taking $f$ from x as long as we arrive a relation like $m-n+1 \leq f^{f(n)}(x) - f^{f(n)-1}(x) \leq m-n+2$(which is possible since $m$ was the first such number and $f(n) > n = f(m)$ ) so we're making $f(x),f^i(x)$ two steps further and this will contradicts $P(n,x)$ and we have $f(x) \geq x+1$ for any $x$ and we're done.

alinazarboland wrote: so we're making $f(x),f^i(x)$ two steps further and this will contradicts $P(n,x)$ and we have $f(x) \geq x+1$ for any $x$ and we're done. how did you conclude this?

Let $P(x,y)$ be the assertion of the problem condition. Firstly , we'll show that for each natural number $x$ , terms of the sequence $f^{i}(x)$ for $i \in \mathbb N$ are pairwise distinct. Suppose not and for numbers $i , n \in \mathbb N$ we have $f^{i}(x)=f^{i+n}(x)$ , so one can easily see that this equality holds for each large enough number $i$ and thus , the sequence $f^{i}(x)$ will be periodic and bounded , which is a contradiction while we have $f^{f(y)}(x)-f(x) \ge y-1$. Now note that there doesn't exist any number $n \in \mathbb N$ such that $f(n)=n$ , because otherwise by plugging $P(n , y)$ for each number $y$ we get $0 \le y \le 1$ which is a contradiction. So for each natural number $x$ by $P(x,1)$ , if we have $f^{f(1)}(x)=f(x)$ then $f(1)=1$ which is a contradiction again. As the result , one can see that : $$f^{f(1)}(x)=f(x)+1 (I) \implies f(f(x)+1)=f(f^{f(1)}(x))=f^{f(1)+1}(x)=f^{f(1)}(f(x))=f(f(x))+1$$So by $(I)$ one can see that the function $f$ is bijective on the set of large enough natural numbers like $\{n , n+1 , ...\}$ and for each number $m \ge n$ we have $f(m+1)=f(m)+1$. Thus while $f(n) > n$ , there exist a natural number $c$ such that the equality $f(m)=m+c$ holds for each number $m\ge n$ and by $P(m , n)$ one can see that : $$ 0 \le n+c-c(f(n))=(1-c)n+c-c^2 \le 1$$So we have $c=1$ and for each natural number $y$ , by $P(n,y)$ we have $0 \le y+1-f(y) \le 1$ and while $f(y) \neq y$ we have $f(y)=y+1$ and we're done.

The only function is $f(x)=x+1$ which works since $$y+f(x)-f^{f(y)}(x)=y+x+1-f^{y+1}(x)=0.$$ Step 1: For any $x$, there does not exist $m>1$ such that $x=f^m(x)$. Proof: Suppose for the sake of contradiction that there does, then the set $\mathcal{O}_x=\{x,f(x),f(f(x)),f(f(f(x))),\ldots\}$ has finitely many terms, so it has a maximal element $M$. Then, taking $y>M$ gives $$y+f(x)-f^{f(y)}(x)\leq 1\implies (M+1)+1-M\leq 1\implies 2\leq 1$$a contradiction. Step 2: $f(x)\geq x+1$. Proof: Assume $f(x)\leq x$ for some $x$, so $f(x)\leq x-1$ since $f(x)\neq x$ from step 1. Substituting $y=1$ gives: $$0\leq 1+f(x)-f^{f(1)}(x)\leq 1\implies f^{f(1)}(x)=f(x)+1\text{ or } f(x)$$but $f^{f(1)}(x)\neq f(x)$ by step 1, so $f^{f(1)}(x)= f(x)+1$. But if $x-f(x)=k$, then $$f^{k(f(1)-1)+1}=f(x)+k=x$$contradicting step 1. Thus, $f(x)\geq x+1$. Step 3: $f(1)=2$. Proof: Since $f(1)\neq 1$ by step 1, assume $f(1)\geq 3$. Then, we consider the sequence of pairwise distinct numbers $$f(x),f(f(x)),\ldots, f^{f(1)}(x)=f(x)+1$$Since $f(1)\geq 3$, we have $f(f(x))<f(x)$, a contradiction to step 2, or $f(f(x))>f^{f(1)}(x)$, which implies the existence of $2\leq j\leq f(1)-1$ such that $f^j(x)>f^{j+1}(x)$, a contradiction to step 2. Thus, $f(1)=2$. Now, reiterating $f^{f(1)}(x)=f(x)+1\implies f(f(x))=f(x)+1$ gives, inductively, $$f(f(1))=f(1)+1\implies f(2)=3\implies \ldots\implies f(f(k))=f(k)+1\implies f(k+1)=k+2$$so $f(x)=x+1$ for all $x$.