lyukhson wrote: Let $\mathbb{Z}_{\ge 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} $ satisfying the relation \[ f(f(f(n))) = f(n+1 ) +1 \] for all $ n\in \mathbb{Z}_{\ge 0}$. nice problem but have usual idea !

Here is a related lemma Lemma: Let $ f:\mathbb{Z}_{\ge 0}\rightarrow\mathbb{Z}_{\ge 0} $ is such that $f^{(k)}(n)=n+a$. Prove that 1. $a$ divides $k$ 2. The set $\{0,1,\ldots, a-1\}$ can be partitioned into tuples $(r_1, r_2,\ldots, r_k)$ such that \[ f(r_1)=r_2, f(r_2)=r_3, \ldots, f(r_{k-1})=r_k, f(r_k)=r_1+a. \] 3. $ f^{(i)}(0)+\ldots+ f^{(i)}(a-1)=1+2+\dots+(a-1)+\frac{a^2}{k}i$ One can note that the function in the problem satisfies $f^{(4)}(n)=n+a$ and also for $g(n)=f(n)+1, $ $g^{(2)}(n)=n+a.$ Using the lemma it is not hard to get $a=4$ and to find the only two solutions: 1. $f(n)=n+1$ 2. $f(n)=\begin{cases}n+1,\ n=2k\\ n+5,\ n=4k+1\\ n-3,\ n=4k+3 \end{cases}$

The idea of the problem: $g(n)=f(n+1)-1$ is also solution.

Let $f^m(n)$ be $f$ iterated on $n$, $m$ times. Let the problem assertion be $P(n)$. Then for $n>0$, from $P(f(n))$ and $P(n-1)$ we get that $f^4(n-1)+1=f(f^3(n-1))+1=f(f(n)+1)+1=f^4(n)$ for all $n>0$, and so $\boxed{f^4(n)=n+c}$ for all $n$ and a constant $c$. From this, $f$ is inyective. We get $f(n+c)=f(f^4(n))=f^5(n)=f(n)+c$, so $\boxed{f(n+c)=f(n)+c}$.

Therefore, we can write $\mathbb{Z}_c$ as a union of disjoint sets of the form $X_n = \{ n, f(n), f^2(n), f^3(n) \}$. This is a partition. (Note that this implies $4 | c$). Let $g : \mathbb{Z}_c \rightarrow \mathbb{Z}$ be a function where $g(n)=f(n)-n$. Then $\sum_{m \in X_n} g(m) = c$. Therefore, if we choose $m$ randomly and uniformly in $\mathbb{Z}_c$, $\mathrm{E}[g(m)]=\frac{c}{4}$.

Notice that if we choose $m$ randomly and uniformly in $\mathbb{Z}_c$, then we are choosing $(m+1) \bmod c$ also randomly and uniformly, so $f(m+1) \bmod c$ is also random and uniform (since it is not hard to verify $f$ is a bijection in $\mathbb{Z}_c$), and so $f(m+1)+1 \bmod c$ is also like this. Also note $f(f(m+1)+1)=f(f^3(m))=f^4(m)=m+c$. Therefore, because of linearity of expectation, $\frac{c}{4} = \mathrm{E}[f(f(m+1)+1)-(f(m+1)+1)] = \mathrm{E}[m+c-(f(m+1)+1)] = \mathrm{E}[(m+1)-f(m+1)] + \mathrm{E}[c-2] = -\frac{c}{4}+(c-2)$ and therefore $\boxed{c=4}$. And so $f(n+4)=f(n)+4$ so we only need to find $f(0),f(1),f(2),f(3)$ to finish. Divide $\mathbb{N}_0$ into sets of size $4$: $\{0,1,2,3\}, \{4,5,6,7\}, \ldots$. Call these sets $4-sets$. If $f(n)=m$ where $m$ is in a previous $4-set$ than $n$, we conclude that $f(n \bmod 4)<0$, contradiction. If $f(n)=m$ where $m$ is two $4-sets$ advanced from $n$, then because of the previous rule, we conclude $f^4(n)>n+4$, contradiction. Therefore, $0 \le f(i) \le 7$ for $i=0,1,2,3$. Now we just do the casework (which I will not write here because it's just casework, nothing interesting) and obtain two solutions: $\boxed{f(n)=n+1}$ and the following convoluted one: $\boxed{f(4k)=4k+1,f(4k+1)=4k+6,f(4k+2)=4k+3,f(4k+3)=4k}$ for all $k \ge 0$.

Done.

have any solution? haha

I need another solution for this problem .

Note: I will refer to $f^k(x)$ to mean $f$ composed $k$ times. So $f^2(x) = f(f(x))$. The FE can now be stated as $f^3(n) = f(n+1) + 1$. Taking $f$ of both sides yields $$f^4(n) = f(f(n)+1) + 1 = f(f(n+1)+1) = f^3(f(n+1)) - 1$$So therefore we see that $f^4(n) + 1 = f^4(n+1)$. It therefore follows that $f^4(n) = n+c$ where $c = f^4(0)$. We will prove that $f$ is injective. Suppose $f(x) = f(y)$. That means $c+x = f^4(x) = f^4(y) = c+y$ and so $x = y$. We can now be certain that $f^{-1}$ exists (the inverse). We can also establish an important relationship by considering $f^4(n) = n+c$. Take $f$ of both sides to get $f^5(n) = f(n+c) = f^4(f(n)) = f(n) + c$. We now break into two cases. Case 1: $c \neq 0$: Notice that we care about the inputs mod $c$, because $f(n+c) = f(n) + c$. Let us first prove that $n, f(n), f^2(n), f^3(n)$ are distinct modulo $c$. Suppose $n \equiv f(n) \pmod{c}$. That would get us into trouble because that means $f(n) = n+kc$ and would yield $f^4(n) = n+4kc$, contradiction. Similarly, if $f^2(n) \equiv n \pmod{c}$, we would get $f^4(n) = n+2kc$ for some $k$. So therefore, each of those must be distinct. I will define the term class to mean a set $n, f(n), f^2(n), f^3(n)$. It is also obvious that these classes have to be mutually exclusive. Note that this easily implies $4|c$. Now let's add!

Now that we get $c = 4$, we can do some bashing. We want to analyze $f(0), f(1), f(2), f(3)$ but this is easy. Bash through and we get $(1, 2, 3, 4)$ or $(1, 6, 3, 0)$ which is weird but whatever. Case 2: $c = 0$. This means $f^4(n) = n$. This means $f^{-1}(n) = f(n+1) + 1$. This means $f^2(n) = f(f(n+1) + 2) + 1$. Then, plug in $n = f(0)$ which is then $0 = f(f(0)+1) + 1$ which is impossible. Sadly, this part took me the longest

$$f^4(n) = f(f(n)+1) + 1 = f(f(n+1)+1) = f^3(f(n+1)) - 1$$Where do you get " f(f(n)+1) + 1 " ?

N.B. $h^n(x)$ will always denote $h$ composed with itself $n$ times (as opposed to $h$ raised to the $n$th power). Obviously $f(n) = n+1$ is a solution. It is easy to verify that $f(0) = 1, f(1) = 6, f(2) = 3, f(3) = 0, f(n+4) = f(n)+4$ is also a solution. We will show that these are the only solutions for $f$. Rewrite the condition as $f^3(n) = f(n+1)+1$. Lemma 1. $f(f(n)+1) = n+c$ for some constant $c \ge 0$. Proof. Note that $f^3(f(n)) = f(f^3(n))$; accordingly, we have $f(f(n)+1)+1 = f(f(n+1)+1)$ for all $n \in \mathbb{Z}_{\ge 0}$. Thus $f(f(n)+1)$ is linear in $n$ and we have $f(f(n)+1) = n + f(f(0)+1)$. Letting $c = f(f(0)+1)$, the result follows. $\blacksquare$ Corollary 1. $g^2(n) = n+c+1$, where $g(n)$ denotes $f(n)+1$. Corollary 2. $f$ is surjective over $[c, +\infty)$. Lemma 2. $f^4(n) = n+c+1$ Proof. Simply note that $f^4(n) = f^3(f(n)) = f(f(n)+1)+1 = n+c+1$. $\blacksquare$ Lemma 3. $f(m+c+1) = f(m)+c+1$ for all $m \in \mathbb{Z}_{\ge 0}$ Proof. Plug in $n = f(m)+1$ into Lemma 1. We get $f(f(f(m)+1)+1) = f(m)+c+1$. Since the LHS equals $f(m+c+1)$, the result follows. $\blacksquare$ Corollary. If $n = y(c+1)+z$ where $y,z$ are integers and $0 \le z < c+1$, we have $f(n) = y(c+1) + f(z)$. Lemma 4. $f$ is injective. Proof. Suppose not; i.e. $f(a) = f(b)$ for some $a<b$. Note that $f(a) = f(b)$ implies $f^3(a) = f^3(b)$ and so $f(a+1) = f(b+1)$. Thus $f(a+n) = f(b+n)$ for all $n \ge 0$; i.e. $f$ is eventually periodic, contradicting Lemma 3. $\blacksquare$ Corollary. $g$ is injective. Now we are ready to do the problem. We will use Lemma 2 and the Corollary 1 to Lemma 1. The basic idea is to look at \[ S = \sum_{n=0}^{c} (f(n) - n) \]and to express this in two different ways. On the one hand, since $f^4(n) = n+c+1$, we have $n,f(n), f(f(n)), f(f(f(n)))$ are distinct modulo $n+c+1$. Thus we have \[S = \frac{1}{4} \sum_{n=0}^{c} ((f(n)-n) + (f^2(n) - f(n)) + (f^3(n) - f^2(n)) + (f^4(n) - f^3(n))) = \frac{1}{4}(c+1)^2. \]On the other hand, since $g^2(n) = n+c+1$, we have $n, g(n)$ are distinct modulo $n+c+1$. Thus we have \[ S = - (c+1) + \sum_{n=0}^{c} (g(n)-n) = -(c+1) + \frac{1}{2}\sum_{n=0}^{c}((g(n) - n) + (g^2(n) - g(n))) = -(c+1) + \frac{1}{2}(c+1)^2 . \]We have \[ \frac{1}{4}(c+1)^2 = -(c+1) + \frac{1}{2}(c+1)^2\]and thus \[ c = 3. \] Now it's not hard to finish. Note that $f(0), f(1), f(2), f(3)$ completely determine $f$. Note that $3 = f(f(0)+1)$, so we must have $f(0) + 1 \le 3$ (otherwise $f(f(0)-3) = -1$, contradiction). Thus $g(0) \le 3$. If $g(0) = 3$, we have $g(3) = 4$, so $f(3) = 3$, contradicting Lemma 2. Similarly, if $g(0) = 1$, we have $f(0) = 0$, contradicting Lemma 2. Thus $g(0) = 2$ and $g(2) = 4$; these imply $f(0) = 1$ and $f(2) = 3$. Now $f$ is surjective over $[3, +\infty)$ so $f(1), f(3) \le 6$. The possibilities for $(f(1), f(3))$ are \[ (0,2), (0,6),(4,2),(4,6), (2,0), (2,4), (6,0), (6,4). \]Checking all of these, we see that the first five cases violate Lemma 2, the sixth case produces the solution $f(n) = n+1$, the seventh case produces the solution $f(0) = 1, f(1) = 6, f(2) = 3, f(3) = 0, f(n+4) = f(n)+4$, and the eighth case violates injectivity. $\blacksquare$

The answer is $f_1(n)=n+1$, and $f_2(n)=n+1$ for $n\equiv 0\pmod 2$, $f_2(n)=n+5$ for $n\equiv 1\pmod 4$, and $f_2(n)=n-3$ for $n\equiv 3\pmod 4$. First we have $f(f(n+1)+1)=f^4(n)=f(f(n)+1)+1$, so define $g(n)=f(f(n)+1)$ gives $g(n+1)=g(n)+1\Rightarrow g(n)=n+g(0)$. So $f^4(n)=g(n+1)=n+g(0)+1$. Let $k=g(0)+1\ge 1$, and $h(n)=f(n)+1$, then $h(h(n))=f(f(n)+1)=n+k$. Note that $h(n+k)=h(h(h(n)))=h(n)+k$. If $f(i)\equiv i \pmod k$, then for any $\ell \in \mathbb{Z}$, $h(i)=i+\ell k\Rightarrow i+k=h(h(i))=h(i+\ell k)=h(i)+\ell k=i+2\ell k \Rightarrow 2\ell =1$ which is is impossible, so for all $0\le i\le k-1$, we have $h(i)=mk+j$ for some $m\in \mathbb{Z}_{\ge 0}$ and $0\le j \le k-1$. If $m\ge 2$ for some $0\le i\le k-1$, then $i+k=h(h(i))=h(mk+j)=h((m-2)k+j)+2k \Rightarrow h((m-2)k+j)=i-k<0$, which is also impossible, so $m\le 1$. Now for all $0\le i,j\le k-1$, $i\neq j$, if $h(i)=j$ then $h(j)=h(h(i))=i+k$, otherwise if $h(i)=k+j$ then $h(j)=h(j+k)-k=h(h(i))-k=i$. In particular, all residues of $k$ can be paired up into pairs $(i,j)$ so that $h(i)\equiv j\pmod k$ and $h(j)\equiv i\pmod k$. So $k$ must be even. Define a residue $i \in \{0,1,\cdots, k-1\}$ to be good if $h(i)=k+j$ and bad if $h(i)=j$ otherwise, for some other residue $j\neq i$. Consider the quantity $$S=\sum^{k-1}_{n=0} h(n+1)=\sum^{k-1}_{n=0} f^3(n)$$Note that if $(i,j)$ is a pair then exactly one of $i$ and $j$ is good, so $h(i)+h(j)=i+j+k \Rightarrow f(i)+f(j)=i+j+k-2$. Furthermore for any $a,b\in \mathbb{Z}_{\ge 0}$, $h(ak+i)+h(bk+j)=ak+h(i)+bk+h(j)=(ak+i)+(bk+j)+k \Rightarrow f(ak+i)+f(bk+j)=(ak+i)+(bk+j)+k-2$. Note that $m\equiv n \pmod k \iff h(m)\equiv h(n)\pmod k \iff f(m)\equiv f(n)\pmod k$, so $\{f^\ell(0), f^\ell(1), \cdots, f^\ell(k-1)\}$ is a complete set of residues modulo $k$ for every $\ell\in \mathbb{N}$. Thus $$S=\sum^{k-1}_{n=0} h(n+1)=\sum^{k-1}_{n=1} h(n)+h(k)=\sum^{k-1}_{n=0} h(n)+k=\sum^{k-1}_{n=0}n+ k(\frac{k}{2})+k$$While we also have $$S=\sum^{k-1}_{n=0}f^3(n)=\sum^{k-1}_{n=0}f^2(n)+(k-2)(\frac{k}{2})=\sum^{k-1}_{n=0}f(n)+2(k-2)(\frac{k}{2})=\sum^{k-1}_{n=0}n+3(k-2)(\frac{k}{2})$$Compare both sides we deduce $k=4$, since $k=g(0)+1\ge 1$. So we have $h(n+4)=h(n)+4 \Rightarrow f(n+4)=f(n)+4$. First, if $0\le i\le 3$ has $h(i)\equiv 0\pmod 4$, then $h(i)=0$ or $h(i)=4$. But $h(i)\neq 0$ otherwise $f(i)=-1$ which is false. So $h(i)=4$. If $i=1$ then $h(1)=4\Rightarrow h(0)=1 \Rightarrow f(0)=0 \Rightarrow 0=f^3(0)=h(1)=4$, false. If $i=3$ then $h(3)=4 \Rightarrow f(3)=3, h(0)=3 \Rightarrow h(4)=7 \Rightarrow 3=f^3(3)=h(4)=7$, false. So $i=2$ and so $h(2)=4\Rightarrow h(0)=2$. So $f(0)=1, f(2)=3$, and so we have $1$ and $3$ are the other pair of residues. If $1$ is bad then $h(1)=3$, then $h(3)=5$, so we get $f(1)=2, f(3)=4$. This gives $f(n)=n+1$ for all $0\le n \le 3$, and hence for all $n\in \mathbb{Z}_{\ge 0}$. Check, we get $n+3=(n+2)+1$, which does works. Otherwise $1$ is good, then $h(1)=7$, then $h(3)=1$, so we get $f(1)=6, f(3)=0$. Check the with the original equation modulo $4$: $f^3(0)=f^2(1)=f(6)=7=f(1)+1$, $f^3(1)=f^2(6)=f(7)=4=f(2)+1$, $f^3(2)=f^2(3)=f(0)=1=f(3)+1$, $f^3(3)=f^2(0)=f(1)=6=f(4)+1$, which is indeed a solution. So we get the desired solution set. $\blacksquare$

mathcool2009 wrote: N.B. $n,f(n), f(f(n)), f(f(f(n)))$ are distinct modulo $n+c+1$. Thus we have \[S = \frac{1}{4} \sum_{n=0}^{c} ((f(n)-n) + (f^2(n) - f(n)) + (f^3(n) - f^2(n)) + (f^4(n) - f^3(n))) = \frac{1}{4}(c+1)^2. \] Can somebody explain this part?

Taha1381 wrote: mathcool2009 wrote: N.B. $n,f(n), f(f(n)), f(f(f(n)))$ are distinct modulo $n+c+1$. Thus we have \[S = \frac{1}{4} \sum_{n=0}^{c} ((f(n)-n) + (f^2(n) - f(n)) + (f^3(n) - f^2(n)) + (f^4(n) - f^3(n))) = \frac{1}{4}(c+1)^2. \] Can somebody explain this part? OK I got it using the original solution here: https://www.imo-official.org/problems/IMO2013SL.pdf

Anyway what was the motivation?(For the second solution.)

Here's a pretty different solution from the above. For any set $S\subseteq \mathbb Z_{\ge 0}$, let $f(S)$ be the image of $S$. Let $Z=\mathbb Z_{\ge 0}$ for convenience. For $a,b\in Z$, let $[a,b] = \{a,a+1, \dots, b\}$ and $[a,\infty) = \{a,a+1, \dots \}$ (so if $a>b$, this set is empty). First, note that $f(f(n+1) + 1) = f^4 (n) = f^3 (f(n)) = f(f(n) + 1) +1$. It then follows from iteration that $f(f(m) + 1) = f(f(n) + 1) + (m-n)$, so $f(m)=f(n)\implies m=n$, so $f$ is injective. Next supppose $n>0$, so $f(n) + 1 = f^3 (n-1)$. It follows that whenever $m\in f(Z), m\neq f(0)$, we have that $m+1\in f(Z)$. It follows that we can split $f(Z)$ into the union of two disjoint intervals $[a, f(0)]\cup [b, \infty)$ for $a\le f(0), b>f(0)$. Now note that $f^3(Z)$ is precisely the set of values $f(1)+1, f(2)+1, \dots$, so $f^3(Z) = [a+1, f(0)] \cup [b+1, \infty)$. Let $S = Z\backslash f(Z)$, so from the injectivity of $f$ it follows that $\{a,b\} = f(Z)\backslash f^3(Z) = f(S) \cup f^2(S)$. Again by injectivity, $f(S)\cup f^2(S) = \emptyset$ and $|S|=|f(S)| = |f^2(S)|$, so comparing magnitudes yields $|S|=1$, meaning we can just let $S=\{c\}$ for some $c\in Z$. We now have two cases. The first case is that $c=0$, so $f(Z) = [1,\infty)$, so $f(Z) = [a,f(0)] \cup [b,\infty)$, where $a=1,b=f(0)+1$. Then clearly $\{a,b\} = \{ f(c), f^2(c)\}$ in some order. In one case we have $f(c) = b\implies f(0) = f(0)+1$, contradiction, so we must have the other case, meaning $f(c)=a, f(a)=b\implies f(0)=1, f(1) = 2$. Now we induct on $n$ to show $f(n)=n+1$, with base cases $n=0,1$ obvious. For the inductive step, we note $f^3 (n-2) = f(n-1) +1\implies (n-1) + 1 + 1 = f^3 (n-2) = f^2(n-1)=f(n)$, as desired. The second case is that $c>0$, in which case since $f(Z) = [a,f(0)]\cup [b,\infty)$ it follows that $c=f(0)+1, a=0, b=f(0)+2 =c+1$. Then once again we have $\{ f(c), f^2(c)\} = \{a,b\} = \{0, f(0)+2\}$. In one case, we have $f^2 (c) =b, f(c)=a\implies f(0)=f(0)+2$, contradiction, so therefore we must have the other case, meaning $f(c) = b, f^2(c) = f(b)=a$. Then $f^3(c) = f(c+1)+1 = f(b) + 1 = a+1=1$. But once again by injectivity, we have $\{ c,f(c), f^2(c), f^3 (c) \} = Z \backslash f^4 (Z)$, and from our previous expression, we have $f^4(n) = f(f(n) + 1) = n+f(f(0)+1)$, so $f^4(Z) = [f(f(0)+1), \infty)$. Since $\{ c,f(c), f^2(c), f^3(c) \} = \{c,f(c),0,1\}$, it follows that $\{c,f(c)\}=\{2,3\}$, so it's pretty clear from our expression for $f(Z)$ that $c=2, f(c)=3$. Now we've established that $f(2)=3, f(3)=0, f(0)=1, f(f(n)+1) = n + f(f(0)+1) = n+3$. This last equality is all we really need to finish. We'll induct on $k$ to show that $f(4k)=4k+1, f(4k+2) = 4k+3, f(4k+3) = 4k, f(4k+1) = 4k+6$. For the base case, $k=0$, we've already shown the first three equalities. From $f(f(3)+1)=6$, we get $f(1)=6$, as desired. For the inductive step, assume we've found the values of $f(0), f(1), \dots, f(4k-1)$. Then $f(f(4k-2) +1) = 4k+1 \implies f(4k)=4k+1$. Meanwhile, $f(f(4k) + 1) = 4k+3 \implies f(4k+2)=4k+3$, and $f(f(4k-3) +1) =4k$ yields $f(4k+3)=4k$. Finally, $f(f(4k+3)+1) = 4k+6\implies f(4k+1)=4k+6$, as claimed. Hence the solutions are $f(n)=n+1$ and $f(n)$ equalling $n+1$ for even $n$, $n-3$ for $n\equiv 3\pmod 4$, $n+5$ for $n\equiv 1\pmod 4$.

Very interesting graph theory problem. Let $S = \operatorname{im} f$ and note that we must have $a\in S\implies a+1$ unless $a = f(0)$, so in particular $S$ is unbounded. Now, if $f(a) = f(b)$ for $a\neq b$ we get $f(a+1) = f(b+1)$, i.e. $f$ periodic, which is not allowed. Thus $f$ is injective, and $S$ is either of the form $\{\alpha, \alpha + 1,\ldots\}$ or $\{\alpha, \alpha+1,\ldots, \beta, \gamma+1, \gamma+2,\ldots\}$, where we let $\beta = f(0)$. Now take the graph on $\mathbb Z_{\geq 0}$ where $a\to b$ if $f(a) = b$. Note that each element has indegree at most one and outdegree exactly one. We define the height of an element $k$ to be the largest $n$ such that there exists a path $a_n \to a_{n-1}\to a_{n-2}\to \cdots \to a_1 \to k$ (possibly infinity if $k$ is in a cycle). Note that $m = \alpha+(\gamma-\beta)$ elements have height $0$, and these each are the sources of chains which are subsets of $\mathbb Z_{\geq 0}$. Consider the $m$ elements with height $1$ or $2$, two from each chain. They are in $S$ but not in $f(f(S))$, so not in $f(\mathbb Z_{>0}+1)$, i.e. not in $\{\alpha+1, \ldots, \beta, \gamma+2,\ldots\}$. There at most $2$ possible such elements, so we conclude $2m \leq 2$ i.e. $m\leq 1$. First we show $m\neq 0$. In that case, we have that $\mathbb Z _{\geq 0}$ is partitioned into a bunch of cycles. But then everything has infinite height, which is a contradiction since zero cannot have height $> 3$. So, $m = 1$. Apply the extension of the $fff$ trick to get $f(f(n+1)+1) = f(f(f(f(n)))) = f(f(n)+1)+1$, i.e. $f(f(n)+1)$ is linear and equal to $n+c$ for some $c$. Then, $g(n) = f(f(f(f(n)))) = n+c$, which means that there can actually be no cycles in the graph since if $f^a(n) = n$. The exception to this is $c = 0$, which implies that $f(f(0)+1) = 0$, or $f(f(f(f(0)))) = 0$. But then $0$ is in a cycle again, which is not allowed. So, there are no cycles, which in particular means we have a large chain. The two cases are $\beta = \gamma$, in which case $\alpha = 1$ and the thing looks like $0 \to \cdots$. Let $\beta = f(0)$, then since $\beta$ is not in $f(f(S))$ we see that $\beta$ is not in $f(\mathbb Z_{>0})$, i.e. $\beta-1\in \{0, \beta\}$, or $\beta = 1$. Now, similarly $f(f(0))-1 \in \{0,\beta\}$, so $f(1) = 2$. We claim that $f(n) = n+1$ by induction in this case. Indeed, we proceed by strong induction, with $n = 0,1 ,2$ clear. For the inductive step, take $n \geq 3$, and we invoke \[ n+1 = f(n-1)+1 = f(f(f(n-2)) = f(f(n-1)) = f(n) \]and done. The other case is $\gamma = \beta+1$, in which case $\alpha = 0$. So, our chain starts with $\beta+1$ and $S = \{0, 1, \ldots, \beta, \beta+2,\ldots\}$. Now, $f(f(S)) = f(\mathbb Z_{>0}) + 1 = \{1, 2, \ldots, \beta, \beta+3,\beta+4, \ldots\}$. So, $f(\beta+1)$ and $f(f(\beta+1))$ are $0, \beta+2$ in some order. Since $f(0) = \beta$, our chain must start with \[ \beta+1\to \beta+2\to 0 \to \beta \]Now $f(f(f(\beta+1))) = f(\beta+2) + 1$, so $\beta = 1$ and we get \[ 2\to 3\to 0 \to 1\to\cdots. \]Now we claim by induction that our solution is \[ A_0 \to A_1 \to \cdots, \]where $A_i = (4i+2)\to (4i+3)\to (4i+0)\to(4i+1)$. In particular, we will show that $A_i$ forms the $i+1,\ldots,i+4$ elements of the chain, with $i = 0$ done. For the inductive step assume it is true for $i$, and we will show that \[ 4i+2\to 4i+3\to 4i+0\to 4i+1\to 4i+6\to 4i+7\to 4i+4\to 4i+5. \]Note that $f(f(f(4i+1))) = f(4i+2)+1 = 4i+4$ so this part is done. Let $f(4i+1) = k$. Then, $f(k) = f(f(f(4i+0))) = f(4i+1)+1 = k+1$. Then, we have \[ 4i+2\to 4i+3\to 4i+0\to 4i+1\to k\to k+1\to 4i+4\to ? \]\[ f(f(f(k))) = f(k+1)+1 = 4i+5. \]Finally, $k = f(f(f(4i+3))) = f(4i+4)+1 = 4i+6$ and we are done. Our solutions are $f(n) = n+1$ and \[ 2\to 3\to 0 \to 1 \to 6 \to 7 \to 4 \to 5 \to \cdots \to 4k+2\to 4k+3\to 4k\to 4k+1\to \cdots. \]

The answers are $f(n) = n+1$ and \[ 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} \]One can check that both of these functions work. So we now have to prove they're the only ones. Part I (involution tricks): We start with the usual involution trick: \[ f^4(n) = f(f(n+1)+1) = f(f(n)+1)+1. \]For $n \ge 1$ the last expression also equals \[ f^4(n) = f\left( f^3(n-1) \right)+1 = f^4(n-1)+1. \]So $f^4$ is linear with slope one, meaning \[ f^4(n) = n+c \qquad (1) \]for some constant $c = f^4(0)$. We have $c \neq 0$ since $c = f^4(0) = f(f(0)+1)+1 \ge 1$ according to the first line. (This is really the only time we use the far-right side of the first line until the end of the solution later.) In particular $f$ is injective and has no fixed points. Next the old involution trick yet again (this time in degree $5$) gives \[f(n+c) = f^5(n) = f(n)+c \qquad (2). \] Because of (1) we can also view $f$ as function modulo $c > 0$, say $f \colon {\mathbb Z}/c \to {\mathbb Z}/c$. In fact: Claim: The function $f$ is a bijection on ${\mathbb Z}/c$. Proof. We have $f^4 \colon {\mathbb Z}/c \to {\mathbb Z}/c$ is the identity, so $f$ is a bijection (with inverse $f^3$). $\blacksquare$ Remark: Although we will not need it, one can show already that all cycles have length $4$. We claim that for each $n$ the elements \[ (n, f(n), f^2(n), f^3(n)) \]are distinct in ${\mathbb Z}/c$. Indeed, if $n$ and $f(n)$ differed by a multiple of $c$, say $f(n) = n+kc$, then (2) would apply in tandem with with (1) to get $f^4(n) = n+ 4kc \neq n+c$, contradiction. Proving this now has the advantage of making Part III later easier. Part II (the system): Now we do a global sum in order to to show $c = 4$. The basic idea is that because of (2), the quantity \[ S = \sum_{n=1}^c \left( f(x_n) - x_n \right) \]is constant for any complete residue system $(x_1, \dots, x_n) \pmod c$. So in particular \begin{align*} S &= \sum_{n=0}^{c-1} \left( f^1(n) - n \right) = A_1 - \frac{1}{2} c(c-1) \\ S &= \sum_{n=0}^{c-1} \left( f^2(n) - f^1(n) \right) = A_2 - A_1 \\ S &= \sum_{n=0}^{c-1} \left( f^3(n) - f^2(n) \right) = A_3 - A_2. \\ S &= \sum_{n=0}^{c-1} \left( f^4(n) - f^3(n) \right) = \frac{1}{2} c(c-1) + c^2 - A_3 \end{align*}where \[ A_k = \sum_{n=0}^{c-1} f^k(n) \qquad k = 1, 2, 3. \]But we have the additional relation \begin{align*} A_3 &= \sum_{n=0}^{c-1} f^3(n) = \sum_{n=0}^{c-1} \left( f(n+1)+1 \right) = A_1 + f(c) - f(0) + c = A_1 + 2c. \end{align*}Solving the system of equations gives $c=4$, $A_1 = 10$, $A_2 = 14$, $A_3 = 18$, $S = 4$. Part III (the surprise): Hence, it remains to determine the values of $f$ on $\{0, 1, 2, 3\}$. This is a finite case check; one of many solutions is presented here. Of course $f(0)+f(1)+f(2)+f(3) = A_1 = 10$. As $n+4=f^4(n)=f(f(n)+1)+1$, we have \[ f(f(n)+1)= n+3. \]We call this property $P(n)$ and use it pin down the small values of $f$. Claim: $f(0) = 1$ and $f(2) = 3$. Proof. Note that $f(f(0)+1) = 3$ by $P(0)$. $f(0) = 0$ fails by taking $n=0$ in the original. $f(0) = 2$ implies $f(3) = 3$, which then gives $3 = f^3(3) = f(4)+1 \implies f(4)=2$ which is wrong. If $f(0) \ge 3$ then $P(0)$ gives $f(f(0)-3) = f(f(0)+1)-4 = -1$, which is absurd. So $f(0) = 1$; thus $f(2) = 3$. $\blacksquare$ We now have $f(1) + f(3) = 6$. We now consider cases on $f(1)$. If $f(1) = 0$, then $P(1)$ gives $f(1) = 4$, wrong. If $f(1) = 2$, we recover $f(n) \equiv n+1$. If $f(1) = 4$, then $P(1)$ gives $f(5) = 4$, wrong since $f(5) = f(1)+4 = 8$. If $f(1) = 6$, we recover the other solution described at the beginning of the proof. This exhausts all cases, so the solutions we claimed are the only ones.

This is quite a long and robust problem. The solution comes in three parts, the first being standard FE tricks, the second being looking at the arrow decomposition, and the last part being a case bash. We claim the solutions are $f(n)\equiv n+1$ and $f(n)\equiv\phi(n)$ where \[\phi(n):=\begin{cases} n+1 & n\equiv 0\pmod{4} \\ n+5 & n\equiv 1\pmod{4} \\ n+1 & n\equiv 2\pmod{4} \\ n-3 & n\equiv 3\pmod{4} \\ \end{cases},\]which we can check both work. Note that the FE implies \[f(f(n)+1)+1=f^3(f(n))=f(f^3(n))=f(f(n+1)+1),\]so \[f^4(n)=f(f(n+1)+1)=f(f(n)+1)+1=f(f(n-1)+1)+2=\cdots=f(f(0)+1)+1+n.\]Let $d=f(f(0)+1)+1\ge 1$, so we have $f^4(n)=n+d$. This already implies that $f$ is injective and that the image of $f$ contains $\{d,d+1,\ldots\}$. Now, we simply note that \[f(n+d)=f(f^4(n))=f^4(f(n))=f(n)+d.\]So we have the two equations $\boxed{f^4(n)=n+d}$ and $\boxed{f(n+d)=f(n)+d}$ for some fixed integer $d\ge 1$. This completes the standard FE tricks portion. Let $G$ be the directed graph such that $a\mapsto b$ if and only if $f(a)=b$. If there was a cycle, say $f^m(x)=x$ for $m\ge 2$, then we would get \[x=f^{4m}(x)=x+4d,\]which is a contradiction. Thus, there are no directed cycles. Furthermore, since $f$ is injective, each vertex has indegree and outdegree $1$. This implies that $G$ looks like a disjoint collection of chains of the form \[x\mapsto f(x)\mapsto f^2(x)\mapsto\cdots.\]We see that the complement of the image of $f$ is finite, so the number of such chains is finite. Let $x_1,\ldots,x_m$ be the starting points of the $m$ chains. Given any $x\in\mathbb{Z}_{\ge 0}$, let $\delta(x)$ denote its distance to the starting point of the chain that it's in. Note that if $f(x)\ge d$, then $f^4(x-d)=x$, so $\delta(x)\ge 4$. This implies that \[x_i,f(x_i),f^2(x_i),f^3(x_i)<d\]and $f^r(x_i)\ge d$ for all $r\ge 4$. Since the complement of the image of $f$ is finite, we see that every residue class mod $d$ is hit, so in particular, $\{f(0),\ldots,f(d-1)\}$ contains all the residue classes. From the above, we see then that the sets \[\{x_i,f(x_i),f^2(x_i),f^3(x_i)\}_{i=1}^m\]partition $\{0,\ldots,d-1\}$ exactly (this implies $d=4m$ in particular). From this, we can see that there is a permutation $\sigma$ on $\{0,1\ldots,d-1\}$ such that \[f(\sigma(i))=i+\epsilon_i d\]where exactly $m=d/4$ of the $\epsilon_i$s are equal to $1$ (these correspond to the $i\in[0,d-1]$ that come from $f^3(x_j)$) and the rest are $0$. We also see that \[f^3(i)=f^{-1}(i+d)=\sigma(i)+(1-\epsilon_i)d\]since if $\epsilon_i=1$, then $f(\sigma(i))=i+d$ and if $\epsilon_i=0$, then $f(\sigma(i)+d)=i+d$. Now, we have $f^3(i)=f(i+1)+1$ for all $i\in\{0,\ldots,d-1\}$, so summing, we see that \[\sum_{i=0}^{d-1}f^3(i)=d+\sum_{i=1}^d f(i)=2d+\sum_{i=0}^{d-1}f(i).\]Thus, \[(0+\cdots+(d-1))+d\left(d-\sum_{i=0}^{d-1} \epsilon_i\right)=2d+(0+\cdots+(d-1))+d\sum_{i=0}^{d-1}\epsilon_i,\]so \[\sum_{i=0}^{d-1}\epsilon_i = \frac{d-2}{2}.\]However, we already know that exactly $d/4$ of the $\epsilon_i$ are $1$ and the rest are $0$, so \[\frac{d}{4}=\frac{d-2}{2},\]or $\boxed{d=4}$. This completes the arrow decomposition portion. We now know that fixing $(i,f(i),f^2(i),f^3(i))=(a,b,c,d)$ to be some permutation of $(0,1,2,3)$ uniquely determines the function, since its graph is just a chain starting from these $4$. This is a finite case check of size $4!=24$, but its actually not that bad if one is careful. Suppose $a=0$. Then, the FE gives $f^3(0)=f(1)+1$, and we have $f(1)\ne 0,1$ (it can't be $0$ since $0$ starts the chain). Also, $f^3(0)\ne 0,1,2$ (since $f(1)\ne 0,1$), so $f^3(0)=3$. Thus, we must have $f(1)=2$, so $(a,b,c,d)=(0,1,2,3)$. This corresponds to the solution $f(n)=n+1$, which is one of the claimed solutions at the beginning. Now, suppose $a=1$. Then, the FE gives $f^3(1)=f(2)+1$, and we have $f(2)\ne 1,2$ (it can't be $1$ since $1$ starts the chain). Also, $f^3(1)\ne 1,2,3$ (since $f(2)\ne 1,2$), so $f^3(1)=0$. This is a contradiction as $f^3(1)=f(2)+1\ge 1$, so there are no solutions in this case. Now, suppose $a=2$. Then, the FE gives $f^3(2)=f(3)+1$, and we have $f(3)\ne 2,3$ (it can't be $2$ since $2$ starts the chain). Also, $f^3(2)\ne 2,3,4$, so $f^3(2)\in\{0,1\}$. However, $f^3(2)\ge 1$, so $f^3(2)=1$, $f(3)=0$, so $(a,b,c,d)=(2,3,0,1)$. This corresponds to the solution $f(n)=\phi(n)$, which is one of the claimed solution at the beginning. Finally, suppose $a=3$. The FE then gives $f^3(3)=f(4)+1=f(0)+2$, and we have $f(0)\ne 0,3$. Thus, $f^3(3)\ne 3,2,5$, so $f^3(3)\le 1$. This is a contradiction since $f^3(3)=f(0)+2\ge 2$, so there are no solutions in this case. This completes the case bash, and thus the solution.

Let $P(n)$ denote the assertion of $n$ to the given functional equation \[ P(n) : f(f(f(n))) = f(n + 1) + 1 \] Denote $f^k(x)$ as the composition of $x$ by the function $f$ as many as $k$ times. Claim 01. $f^4(n) = n + c$ for a constant $c$. Proof. Notice that $P(f(n))$ ad $P(f(n - 1))$ gives us \[ f^4(n) = f^3 ( f(n)) = f(f(n) + 1) + 1 = f( f^3 (n - 1)) + 1 = f^4(n - 1) + 1 \]Therefore, we can have $f^4(n) = f^4(0) + n$. Denote $f^4(0) = c$, then we have $f^4(n) = n + c$. Claim 02. $f$ is injective. Proof. If $f(a) = f(b)$, then we have \[ a + c = f^4 (a) = f^4 (b) = b + c \]Therefore, we must have $a = b$, proving that $f$ must be injective. Claim 03. $f(n + c) = f(n) + c$. Proof. Notice that \[ f(n + c) = f( f^4 (n) ) = f^5 (n) = f^4 (f(n)) = f(n) + c \] Claim 04. $c$ is divisible by $4$. Proof. Here's the graph theory portion. We claim that \[ n, f(n), f(f(n)), f(f(f(n))) \]are distinct in $\mathbb{Z}_c$. Suppose $f(n) \equiv n \ (\text{mod} \ c)$, take $f(n) = n + kc$. Therefore, \[ f(f(f(f(n)))) = f(f(f(n + kc))) = f(f(f(n))) + kc = f(f(n)) + 2kc = f(n) + 3kc = n + 4kc \]This gives us $4k = 1$, a contradiction. Suppose $f(f(n)) \equiv n \ (\text{mod} \ c)$, take $f(f(n)) = n + kc$. Therefore, \[ f(f(f(f(n)))) = f(f(n + kc)) = n + 2kc \]This gives us $2k = 1$, a contradiction. Suppose $f(f(f(n))) \equiv n \ (\text{mod} \ c)$, take $f(f(f(n))) = n + kc$. Therefore, \[ f(f(f(f(n)))) = f(n + kc) = f(n) + kc \]This gives us $f(n) \equiv n \ (\text{mod} \ c)$, which has been done before. By injectivity, we get that $\{ n, f(n), f(f(n)), f(f(f(n)))$ are distinct in $\mathbb{Z}_c$. Consider the graph $G$ where every vertex denote a residue in $\mathbb{Z}_c$ and connect $a \to b$ when $f(a) = b$. We get that we can partition graph $G$ into distinct cycles of length $4$. (Notice that by injectivity, no two cycles will coincide.) Therefore, $4 | c$. We'll first consider the case where $c = 0$: This is immediate as \[ n = f^4(n) = f(f(n+1) + 1) = f(f(n) + 1) + 1 \]Plug $n = 0$ to the above equation, and we have $f(f(0) + 1) = -1$, a contradiction as $f : \mathbb{Z}_0 \to \mathbb{Z}_0$. Claim 05. If $c \not= 0$, then $c$ must be $4$. Proof. This is one of the best arguments I've seen in a while. Notice that $\{ f(0), f(1), f(2), \dots, f(c - 1) \}$ and $\{ 0 , 1 , 2 , \dots, c - 1 \}$ are the same in $\mathbb{Z}_c$. We'll try to double count the values of \[ Q(k) : \sum_{i = 0}^{c - 1} f(i) - i \]which must be constant due to obvious reasons. Denote $S_m = \sum_{i = 0}^{c - 1} f^m (i) $. By assertion $Q(S_m)$, we have \[ S_{m + 1} - S_m \ \text{being constant} \]Now, notice that \[ S_4 - S_3 = S_3 - S_2 = S_2 - S_1 = S_1 - S_0 \]Therefore, we have $S_4 = 4S_1 - 3S_0 \ $ by easy manipulation and \[ S_4 = \sum_{i = 0}^{c - 1} f^4(i) = \sum_{i = 0}^{c - 1} ( i + c ) = S_0 + c^2 \]We then have $4 (S_1 - S_0) = c^2$. Now, notice that $P(k)$ gives us \[ \sum_{i = 0}^{c - 1} f(f(f(i))) = \sum_{i = 0}^{c - 1} ( f(i + 1) + 1 ) = c + \sum_{i = 1}^c f(i) = 2c + \sum_{i = 0}^{c - 1} f(i) \]by considering $f(c) = f(0) + c$. This means that $S_3 - S_1 = 2c$. But, we know that \[ 2c = S_3 - S_1 = 2(S_1 - S_0) = \frac{1}{2} ( 4 (S_1 - S_0) ) = \frac{1}{2} c^2 \]Therefore, $c = 4$. Now, it's time for construction - bash! Since $f(n + c) = f(n) + c$, we just need to consider the graph of vertex $0,1, 2, 3$. We'll consider all of the following operation in $\mathbb{Z}_c$: If $0 \to 2 \to 1 \to 3 \to 0$, then $f(1) = f^3(0) = f(1) + 1$, a contradiction. If $0 \to 2 \to 3 \to 1 \to 0$, then $f(2) = f^3(1) = f(2) + 1$, a contradiction. If $0 \to 3 \to 1 \to 2 \to 0$, then $f(3) = f^3(2) = f(3) + 1 $, a contradiction. If $0 \to 1 \to 3 \to 2 \to 0$, then $f(2) = f^3(1) = f(2) + 1$, a contradiction. We are left the case where $0 \to 1 \to 2 \to 3 \to 0$ and $0 \to 3 \to 2 \to 1 \to 0$. Case 01. $0 \to 3 \to 2 \to 1 \to 0$. Proof. If $f(1) = 0$, then \[ 0 = f(0 + 1) = f(f(1) + 1) = f(f(0) + 1) + 1 \]a contradiction. Since $f$ is surjective for all values $\ge 4$, then we must have $f(1) = 4$. $P(0)$ gives us \[ f^3(0) = f(1) + 1 = 5\]If $f(0) = 7$, then we must have $f^2(7) = f^3(0) = 5$, then $8 = 4 + f(1)= f(5) = f^3(7) = f(8) + 1$. This gives us $f(8) = 7$, which gives us $f(0) = -1$, a contradiction. Therefore, we must have $f(0) = 3$. If $f(2) = 5$, then \[ f(6) + 1 = f^3(5) = f^4(2) = 2 + 4 = 6 \]Hence, $f(6) = 5$, giving us $f(2) = 1$, a contradiction. Therefore, we must have $f(2) = 1$. Since \[ f(f(3) + 1) = f(f(2) + 1) + 1 = 2 \]and $f(3)$ is the minimal value of $2$ mod $4$ in all values of $f(4a + 3)_{a \ge 0}$. Hence, we must have $f(3) = 2$. But easy checking gives us \[8 = f(0) + 5 = f(4) + 1 = f^3(3) = f^2(2) = f(1) = 4\]a contradiction. Case 02. $0 \to 1 \to 2 \to 3 \to 0$. Proof. We consider two cases: If $f(3) = 0$ or $f(3) = 4$. If $f(3) = 0$, then we must have \[ f(1) + 1 = f^3(0) = f^4(3) = 7 \]and hence $f(1) = 6$. Notice that $f(f(1) + 1) = f(f(0) + 1) + 1$. This gives us $f(f(0) + 1) = 3$. Since $f(2) \equiv 3 \ (\text{mod} \ 4)$ and is the minimum among all values of $f(4a + 2)_{a \ge 0}$. Hence, $f(2) = 3$. This gives us $f(f(0) + 1) = f(2)$, which by injectivity gives us $f(0) = 1$. To your surprise! By the property $f(n + 4) = n + 4$, we have that $$\boxed{f(n) =\begin{cases} n + 1 & \text{if} \ n \equiv ( 0\ \text{mod} \ 2) \\ n + 5 & \text{if} \ n \equiv (1 \ \text{mod} \ 4) \\ n - 3 & \text{if} \ n \equiv (3 \ \text{mod} \ 4) \end{cases}}$$is a solution. (Just check if you don't believe it!) Now, if $f(3) = 4$, we have that \[ f(9) + 1 = f^3(8) = f^4(7) = 11 \]Hence, $f(9) = 10$. This gives us $f(1) = 2$. Hence, \[ f(3) = f(f(1) + 1) = f(f(0) + 1) + 1 \]This gives us $f(f(0) + 1) = 3$. Since $f(2)$ is the minimal value of $f(4a + 2)_{a \ge 0}$ and has the value of 3 modulo 4, we have that $f(2) = 3$. By injectivity, we have $f(0) = 1$, and therefore by the property $f(n + 4) = f(n) + 4$, we have that $$\boxed{f(n) = n + 1}$$is a solution. Al Fine!

Solved with eisirrational. First note that \begin{align*} f^4(n)&=f\left(f^3(n)\right)=f(f(n+1)+1)\\ &=f^3(f(n+1))-1=f^4(n+1)-1. \end{align*}Hence $f^4(n)=n+c$ for some $c$; as a corollary, $f$ is injective. By the same trick, we have $f(n+c)=f^5(n)=f(n)+c$. In what follows, we draw an arrow from $a$ to $b$ whenever $f(a)=b$. Claim: Each nonnegative integer is an element in some infinite chain of the form \[w\to x\to y\to z\to w+c\to x+c\to y+c\to z+c\to\cdots,\]where $w$, $x$, $y$, $z$ are distinct nonnegative integers less than $c$. Proof. This follows from $f^4(n)=n+c$. All elements of the chain are distinct, since the chain grows arbitrarily large, and otherwise it would be periodic. It remains to see that $w,x,y,z<c$. Assume, for example, that $z\ge c$; then $f(z-c)=w$ by injectivity, so we may instead start our chain at $z-c$. The same argument applies for $w$, $x$, $y$, so we may suitably choose $w$ so that $w,x,y,z<c$. $\blacksquare$ It follows that $4\mid c$, since we can partition the elements of $\{0,1,\ldots,c-1\}$ into subsets $\{w,x,y,z\}$ of size $4$ such that $w\to x\to y\to z$. Claim: $c=4$. Proof. By Claim 1, for $c/4$ of the nonnegative integers $n<c$ is $f(n)<c$; analogously for $3c/4$ of the nonnegative integers $n<c$ is $f^3(n)<c$. Summing over the given functional equation, \begin{align*} \frac{c(c-1)}2+\frac{3c^2}4&=\sum_{n=0}^{c-1}f^3(n)=c+\sum_{n=1}^cf(n)\\ &=2c+\sum_{n=0}^{c-1}f(n)=\frac{c(c-1)}2+\frac{c^2}4+2c. \end{align*}This solves to $c=4$. $\blacksquare$ What remains is a finite case check: there is a single chain $w\to x\to y\to z\to\cdots$ (with $\{w,x,y,z\}=\{0,1,2,3\}$) that covers all nonnegative integers. We take cases: If $w=0$, then $z=f(1)+1\ge3$, so $z=3$ and $f(1)=2$; the corresponding chain is $0\to1\to2\to3\to\cdots$. If $w=1$, then $z=f(2)+1\ge1$. Clearly $z\ne1$; $z\ne2$ since $f(2)\ne1$; and $z\ne3$ since $f(2)\ne2$. If $w=2$, then $z=f(3)+1\ge1$. Clearly $z\ne2$; $z\ne3$ since $z\ne f(3)+1$; and $z=1$ implies $f(3)=0$, and the corresponding chain is $2\to3\to0\to1\to\cdots$. If $w=3$, then $z=f(4)+1\ge5$. In summary, the only valid chains are $0\to1\to2\to3\to\cdots$ and $2\to3\to0\to1\to\cdots$, so the answer is \[ \boxed{f(n)=n+1}\quad\text{or}\quad\boxed{f(n)= \begin{cases} n+1&\text{if $n$ even}\\ n+5&\text{if $n\equiv1\pmod4$}\\ n-3&\text{if $n\equiv3\pmod4$} \end{cases} }. \]Both work, so we are done.

lyukhson wrote: Let $\mathbb{Z}_{\ge 0}$ be the set of all nonnegative integers. Find all the functions $f: \mathbb{Z}_{\ge 0} \rightarrow \mathbb{Z}_{\ge 0} $ satisfying the relation \[ f(f(f(n))) = f(n+1 ) +1 \]for all $ n\in \mathbb{Z}_{\ge 0}$. Let $P(x)$ denote the statement of the problem or the assertion of the problem. $P(f(x)) \implies f(f(x+1)+1)=f(f(x)+1)+1$. Consider a function $g$ such that $f(f(x)+1)+1=g(x)$. We see that here, $g(n+1) = g(n)+1$ and since the domain consists of only integers, we're free to say that $g(x) = x + c$ for some integer constant $c$ or in other words, $f(f(x)+1)=x+c-1$. Now, using the lemma mentioned by tash : tash wrote: Here is a related lemma Lemma: Let $ f:\mathbb{Z}_{\ge 0}\rightarrow\mathbb{Z}_{\ge 0} $ is such that $f^{(k)}(n)=n+a$. Prove that 1. $a$ divides $k$ 2. The set $\{0,1,\ldots, a-1\}$ can be partitioned into tuples $(r_1, r_2,\ldots, r_k)$ such that \[ f(r_1)=r_2, f(r_2)=r_3, \ldots, f(r_{k-1})=r_k, f(r_k)=r_1+a. \] 3. $ f^{(i)}(0)+\ldots+ f^{(i)}(a-1)=1+2+\dots+(a-1)+\frac{a^2}{k}i$ One can note that the function in the problem satisfies $f^{(4)}(n)=n+a$ and also for $g(n)=f(n)+1, $ $g^{(2)}(n)=n+a.$ Using the lemma it is not hard to get $a=4$ and to find the only two solutions: 1. $f(n)=n+1$ 2. $f(n)=\begin{cases}n+1,\ n=2k\\ n+5,\ n=4k+1\\ n-3,\ n=4k+3 \end{cases}$ We get that the solutions are : $f(x) = x + 1$ or $f(x) = x + 1$ if $x$ is even and $f(x) = x + 5$ and $f(x) = x-3$ if $x \equiv 1$ and $3$ $\pmod{4}$ respectively.

First, note that\[f^4(n) = f^3(f(n)) = f(f(n) + 1) + 1 = f(f^3(n-1)) + 1 = f^4(n-1) + 1\]so it follows that the function $f^4(n)$ is linear; so we may write $f^4(n) = n + c$ for a constant $c = f^4(0)$. Here we note that $f$ is injective, since if $f(a) = f(b)$, then\[b + c = f^3(f(b)) = f^3(f(a)) = a + c \implies a = b.\]Furthermore, we may also obtain $f(n+c) = f(f^4(n)) = f^4(f(n)) = f(n) + c$. Note that $f^4(0) = c = 0$ is impossible since that would mean $f^4(n) = n$ and thus $f$ would be a bijection. Hence, an inverse $f^{-1}$ would exist and be defined for all $n$ thus $f^{-1}(n) = f^3(n) = f(n+1) + 1$. Plugging in the value $n = f(0)$ would yield\[0 = f^{-1}(f(0)) = f(f(0) + 1) + 1 \geq 1\]which would indeed be a contradiction. Otherwise, $c \neq 0$, and we claim that $\{n, f(n), f^2(n), f^3(n)\}$ are all different modulo $c$ for all $n$. If not: If $f(k) \equiv k \pmod c$ for some $k$, then setting $f(k) = k + mc$ gives\[f^4(k) = f^3(k + mc) = f^2(f(k) + mc) = f(f^2(k) + mc) = f^3(k) + mc\]since $f(n+c) = f(n) + c$ for all $n$, through induction, gives\[f(n + mc) = f(n + (m-1)c) + c = \ldots = f(n) + mc\]for all $n, m$. An unwrap yields\[f^3(k) + mc = f^2(k + mc) + mc = f^2(k) + 2mc = f(k) + 3mc = k + 4mc = f^4(k) = k + c\]which implies $4m = 1$, impossible. $\square$ If $f^2(k) = k$ for some $k$, then setting $f^2(k) = k + mc$ gives\[k + c = f^4(k) = f^2(k + mc) = f(f(k) + mc) = f^2(k) + mc = k + 2mc\]hence $2m = 1$, impossible. $\square$ If $f^3(k) = k$ for some $k$, then setting $f^3(k) = k + mc$ gives\[k + c = f^4(k) = f(k + mc) = f(k) + mc\]so $m = 1$. Thus $k + c = f^3(k) = f^4(k)$ which has been covered in the first case. $\square$ Thus, the chain $n, f(n), f^2(n), \ldots$ for any fixed $n$ has period $4$ modulo $c$, since $f^4(n) = n + c$ in general. Clearly, no two chains can have overlapping residues due to injectivity, so $\{0, 1, \ldots , c-1\}$ can be partitioned into some collection of disjoint chains (each covering $4$ residues), and thus $4 \mid c$. \newpage We will go on further to prove that in fact, $c = 4$. Notice that,\[\sum_{i = 0}^{c-1} f^3(i) = \sum_{i = 1}^{c} (f(i) + 1) = 2c + \sum_{i = 0}^{c-1} f(i) \implies \sum_{i = 0}^{c-1} f^3(i) - \sum_{i=0}^{c-1} f(i) = 2c.\]Note that each of the elements of $\{0, 1, \ldots , c-1\}$ takes on the role of one of $\{f^0(\ell), f^1(\ell), f^2(\ell), f^3(\ell)\}$ for some chain defined by $\ell$. Since the chains are disjoint, exactly $\tfrac{c}{4}$ of them take on the role of each one. Denote set $S_0$ as the set of elements of $\{0, 1, \ldots , c-1\}$ that takes the role of some $f^0(\ell)$, and also similarly the sets $S_1, S_2, S_3$. Write\begin{align*}\sum_{i = 0}^{c-1} f^3(i) &= \sum_{i \in S_0} f^3(i) +\sum_{i \in S_1} f^3(i) +\sum_{i \in S_2} f^3(i) +\sum_{i \in S_3} f^3(i)\\ &= \sum_{i \in S_3} i + \sum_{i \in S_0} (i + c) + \sum_{i \in S_1} (i + c) + \sum_{i \in S_2} (i + c)\\&= (0 + 1 + \ldots + (c-1)) + \frac{3c^2}{4}\end{align*}\begin{align*}\sum_{i = 0}^{c-1} f(i) &= \sum_{i \in S_0} f(i) +\sum_{i \in S_1} f(i) +\sum_{i \in S_2} f(i) +\sum_{i \in S_3} f(i)\\ &= \sum_{i \in S_1} i + \sum_{i \in S_2} i + \sum_{i \in S_3} i + \sum_{i \in S_0} (i + c)\\&= (0 + 1 + \ldots + (c-1)) + \frac{c^2}{4}\end{align*}hence $\tfrac{3c^2}{4} - \tfrac{c^2}{4} = 2c$ and indeed, $c = 4$. Now, we finish the problem. For any chain $f^0(\ell), f^1(\ell), \ldots$ it must be defined by $\{f^0(\ell), f^1(\ell), f^2(\ell), f^3(\ell)\} = \{0, 1, 2, 3\}$. The rest of the chain is automatically generated by $f^4(n) = n + c = n + 4$. If $f^0(\ell) = \ell = 0$, then $f^3(0) = f(0 + 1) + 1 = f^1(1) + 1$. Clearly $1 = f^2(0)$ is implausible, and $1 = f^3(0)$ implies that $f^4(0) = 0$, which is false. Thus, $1 = f(0)$. Furthermore, we know $f^3(0) = f^2(0) + 1$ so $f^3(0)$ must be $3$, and $f^2(0)$ must be $2$. The chain must be $0, 1, 2, 3, \ldots$ and so on. If $f^0(\ell) = \ell = 1$, then $f^3(1) = f(1 + 1) + 1 = f^1(2) + 1$. If $2 = f^1(1)$, then $f^3(1) - f^2(1) = 1$, which is not possible since $f^3(1), f^2(1) \in \{0, 3\}$. Clearly $2 = f^2(1)$ is implausible, and also, $2 = f^3(1)$ implies that $f^4(1) = 1$, which is false. This case is impossible. If $f^0(\ell) = \ell = 2$, then $f^3(2) = f(2 + 1) + 1 = f^1(3) + 1$. Clearly $3 = f^2(2)$ is implausible, and $3 = f^3(2)$ implies that $f^4(2) = 2$, which is false. Thus, $3 = f(0)$. Furthermore, we know $f^3(0) = f^2(0) + 1$ so $f^3(0)$ must be $1$, and $f^2(0)$ must be $0$. The chain must be $2, 3, 0, 1, \ldots$ and so on. If $f^0(\ell) = \ell = 3$, then $f^3(3) = f(3 + 1) + 1 = f(0) + 5$. Note that $f^3(3) - f(0)$ must always differ by at most $4$, so this is impossible. Thus, the only two possible chains are\[0, f^1(0), f^2(0), \ldots = \{0, 1, 2, 3, 4 \ldots\} \text{ and } 2, f^1(2), f^2(2), \ldots = \{2, 3, 0, 1, 6 \ldots\}.\]We can extrapolate the answers from these two chains. From the first chain, we get $f(0) = 1, f(1) = 2, f(2) = 3, f(3) = 4$. The rest of the function is automatically generated by $f^4(n) = n + 4$, so in this case, the solution of\[\boxed{f(n) = n + 1}\]is reached. From the second chain, we get $f(2) = 3, f(3) = 0, f(0) = 1$, and $f(1) = 6$. Similarly, the rest of the function is automatically generated by $f^4(n) = n + 4$, so this case yields the solution of\[\boxed{f(n) = \begin{cases} n+1 & \text{ if }n \equiv 0 \pmod 4\\ n+5 & \text{ if }n \equiv 1 \pmod 4\\ n+1 & \text{ if }n \equiv 2 \pmod 4\\ n-3 & \text{ if }n \equiv 3 \pmod 4. \end{cases}}\]These two solutions both clearly work, so we are done. $\blacksquare$ brain orgasm

Notice $f(f(f(f(n)))) + 1 = f(f(n+1)+1)+1 = f(f(f(f(n+1))))$ so $f(f(f(f(n)))) = n+c$ for some constant $c \geq 0$. Consider $c = 0$, then $f$ forms only $4$-cycles and $2$-cycles. Notice if $n$ is the local max of a cycle then so is $n + 1$, but not every number is a local max so contradiction. Consider $c > 0$, then $c$ is injective whose chains only begin between $0$ and $c-1$ inclusive. Thus $f$ forms a draconic chain, a function dictated by a finite set of chains. A quasi-linear function. We know each chain takes four of the$c$ starting values. Anyways, simply sum the given over $n = 0$ to $n = c-1$ to get $\frac{1}{2}c^2 = 2c$ so $c = 4$. Casework on the order of the first four elements of the chain gives two solutions: $f(n) = n + 1$ and $f(n) = \begin{cases} n + 1 & 2 \mid n \\ n + 5 & 4 \mid n - 1 \\ n - 3 & 4 \mid n + 1 \\ \end{cases}$

Let $P(n)$ be the assertion. Note that $f(P(n-1))+1$ gives $f(f(n)+1)+1=f^4(n-1)+1$. On the other hand, $P(f(n))$ gives $f^4(n)=f(f(n)+1)+1$ so \[f^4(n)=n+c\]where $c=f^4(0)$. Now, $f(n)+c=f^5(n)=f(n+c)$. If $f(a)\equiv f(b)\pmod c$ then $f^4(a)\equiv f^4(b)\pmod c$ so $a\equiv b\pmod c$. Thus, for any list $\{x_1,x_2,\dots, x_c\}$ that forms a complete residue system $\pmod c$ then $\{f(x_1),f(x_2),\dots, f(x_c)\}$ also does. Let $g(x)=f(x)-x$. Note that $g(n+c)=f(n+c)-(n+c)=f(n)-n=g(n)$. We have if $a\equiv b\pmod c$ then $g(a)=g(b)$. If $\{x_1,x_2,\dots, x_c\}$ forms a complete residue system $\pmod c$ then there exists a permutation, $\{x_{\sigma_1},x_{\sigma_2},\dots, x_{\sigma_c}\}$ such that $f(x_{\sigma_1})\equiv x_1\pmod c$. Then, \begin{align*} g(x_1)+g(x_2)+\dots + g(x_c) &= g(f(x_{\sigma_1}))+g(f(x_{\sigma_2}))+\dots +g(f(x_{\sigma_c})) \\ &= g(f(x_1))+g(f(x_2))+\dots+g(f(x_c))\end{align*}In particular, using on $\{0,1,\dots, c-1\}$, we have \[g(0)+g(1)+\dots + g(c-1)=g(f(0))+g(f(1))+\dots +g(f(c-1))=g(f^2(0))+g(f^2(1))+\dots +g(f^2(c-1))\]Let $S=f(0)+f(1)+\dots+ f(c-1)$ then \[f^3(0)+f^3(1)+\dots + f^3(c-1)=f(1)+1+f(2)+1+\dots + f(c)+1=c+S+f(c)-f(0)=S+2c\]and Thus, \[2c=g(f^2(0))+g(f(0))+\dots + g(f^2(c-1))+g(f(c-1))=2\left(S-\frac{c(c-1)}{2}\right)\]implying $2S=c(c+1)$. On the other hand, \[g(0)+g(1)+\dots + g(c-1)=g(f^3(0))+g(f^3(1))+\dots +g(f^3(c))\]Which gives \[S-\frac{c(c-1)}{2}=c^2+\frac{c(c+1)}{2}-S-2c\]so $2S=c(2c-3)$. Either $c=0$ or $c=4$. If $c=0$ then $f(0)=0$ so $P(0)$ gives $f(1)=-1$, absurd. We know that $c=4$. It remains to determine $f(0),f(1),f(2),f(3)$. We have $S=f(0)+\dots + f(3)=10$. We have $f^4(0)=f(f(0)+1)+1$ so $f(f(0)+1)=3$. If $f(0)\ge 3$ then $f(f(0)-3)= -1$, absurd. If $f(0)=2$ then $f(3)=3$, so $f^3(3)=f(4)+1=3$, absurd. We already know $f(0)\neq 0$, so $f(0)=1$, implying $f(2)=3$. Thus, $f(n)=n+1$ for all even $n$. We have $f(1)+f(3)=6$. Note that $f(1)$ and $f(3)$ are both even. If $f(1)=0$ then $5=f^4(1)=f(1)+1$, absurd. If $f(1)=4$ then $5=f(5)+1$ so $f(1)=0$, absurd. $f(1)=2$ and $f(1)=6$ both give valid solutions, which are \[f(n)=n+1\]and \[ f(n) = \begin{cases} n+1 & n \equiv 0\pmod 4 \\ n+5 & n \equiv 1 \pmod 4 \\ n+1 & n \equiv 2\pmod 4 \\ n-3 & n \equiv 3 \pmod 4. \end{cases} \]

Claim: $f^4(x-1)+1 = f^4(x)$ Proof. Note that \[ f^4(x) = f^3(f(x)) = f(f(x) + 1) + 1 > 0 \]but also that \[ f^4(x) = f(f^3(x)) = f(f(x+1)+1) \]Thus, $f^4(x-1) = f(f(x)+1) = f^4(x) - 1$ $\blacksquare$ Inductively, this means that $f^4(x) = f^4(0) + x$ As such, $f$ is injective. Let $c = f^4(0) > 0$. Claim: $f(x + c) = f(x) + c$. Proof. Consider $f^5(x)$ to get that \[ f^5(x) = f^4(f(x)) = f^4(0) + f(x) \]and that \[ f^5(x) = f(f^4(x)) = f(x + f^4(0)) \]Thus, if we let $c = f^4(0) > 0$ then $f(x + c) = f(x) + c$. $\blacksquare$ Since $f$ is injective, it follows that the residues $\pmod{c}$ form a bijection. As such, it follows that $f(x) - x$ only depends on its residue. Thus, \[ S = \sum_{i=0}^{c-1} (f(x_i) - x_i) \]is constant if $(x_0, x_1, \dots)$ is a complete residue system. Claim: $c = 4$ Proof. It follows that \[ 4 \cdot S = \sum_{i=0}^{c-1} (f^4(i) - i) = c^2, \]meaning that $S = \frac{c^2}{4}$. Then, since \[ c = \sum_{i=0}^{c-1} (f^3(n) - f(n + 1)) = \sum_{i=0}^{c-1} (f^3(n) - f(n)) - c = 2 \cdot S - c \]it follows that $S = c$. Thus, $c = \frac{c^2}{4}$ and $c = 4$. $\blacksquare$ As such, $\{f(0), f(1), f(2), f(3)\}$ is the same as $\{0, 1, 2, 3\}$ with one of the elements having $4$ added to it. Furthermore, since $f^4(x) = x + 4$, it follows that no residue maps to itself. Similarily $f$'s graph can not consist of two cycles, and can only be one $4$ element cycle. Testing the $6$ cycles means that when considered as an element of $S_4$, $f$ is either $(0123)$ or $(3210)$. Manually checking gives that for the first case, either $f(x) = x + 1$ or \[ f(x) = \begin{cases} x - 3 & x \equiv 3 \pmod{4} \\ x + 1 & x \ne 0, 2 \pmod{4} \\ x + 5 & x \equiv 1 \pmod{4} \end{cases}. \]

The answer is $\boxed{f(n)=n+1}$ and \[\boxed{f(n)=\begin{cases}n+1&n\text{ is even}\\n-3&n\equiv 3\pmod 4\\n+5&n\equiv 1\pmod 4\end{cases}}.\]It is not hard to check that these work, so we will show that these are the only solutions. Note that \[f(f(f(f(n))))+1=f(f(n+1)+1)+1=f(f(f(f(n+1)))),\]so there exists some $c_0\in\mathbb{Z}_{\ge 0}$ such that $g:=f^4$ satisfies $g(n)=n+c_0$. Claim. We have $c_0\in\{0,4\}$. Proof. Assume that $c_0\ne 0$. Considering the arrows graph of $f$, we get that $4\mid c_0$, so let $c_0=4c$.Also by considering the arrows graph, we get that $f$ reaches all but exactly $c$ nonnegative integers. Now let $h(n):=n+1$. Then we also have \[f^4 = (f\circ h)^2.\]Therefore, $f\circ h$ reaches all but exactly $2c$ nonnegative integers, meaning that $f$ misses at least $2c-1$ nonnegative integers. Thus $c\ge 2c-1$, so $c\le 1$. $\blacksquare$ Case 1. $c_0=0$. Then $(f\circ h)^2 (n)=n$. We claim that this is not possible for $n=f(f(0)+1)$. In fact, since $f$ is a bijection(since $g$ is the identity), we would need to have \[h(f(h(f(f(0)+1))))=f(0)+1\Longrightarrow h(f(f(0)+1))=0,\]absurd. Case 2. $c_0=4$. Then $f$ cycles through all four residues mod $4$ then adds $4$ to the cycle, etc. Thus $f$ is injective. We have \[f(h(f(h(3))))=f(h(f(4)))\in f(h(\{5,6,7,9,10,11\}))\in f(\{6,7,8,10,11,12\}),\]so \[f(f^3(3))\in f(\{6,7,8,10,11,12\})\Longrightarrow f(f(f(3)))\in\{6,7,8,10,11,12\}.\]But $f(f(f(3)))<8$, and $f(f(f(3)))\ne 7$, so $f(f(f(3)))=6$, so $3+4=f(6)$, so $f(6)=7$, so $f(2)=3$. This would also need $f(4)$ to be $5$, so $f(0)=1$. This indeed shows that the claimed solutions are the only ones, so we are done. $\blacksquare$

Outline of my proof:- Prove that $f$ is injective. Prove that if $m$ is the minimum value among $f(1),f(2),......$All values $\geq m$ are in range of $f$ Prove that there exist a positive integer $c$ such that $f^4(x)=x+c$ by abusing the involution trick And then again abuse the involution trick to get $f(x+c)=f(x)+c$ So then $\{f(0),f(1),....,f(c-1)\}$ are distinct modulo $c$ and uniquely determine $f$ Observe the numbers $\{c,c+1,......\}$ are in the range of $f$ so each $f(i) \leq 2c-1$ where $i < c$ Prove there exist a non negative integer $b$ such that $f(x) \geq c \iff x \geq b$ Observe $f(f(f(x))) \leq c \iff f(x+1) \leq c-1 \iff x+1<b$ Observe $f(f(f(x))) \leq c-1 \iff f(f(x)) <b$ and keep in mind u have $f^3(x)=c$ as well thats at max one more solution So let $A$ be the set of all solutions to the first ineuqliaty and $B$ for second then $A=B$ Prove that $f(x)<c$ must have atleast one solution Use this to bound $c$ and finish the problem

Let $f^4(0)=c$ and we have \begin{align*} & f(f(n+1)+1)=f(f(n)+1)+1 \iff f^4(n)=f^4(n-1)+1 \text{ } \left(\spadesuit \right) \end{align*}Through induction we get that \[f^4(n)=n+c \implies f(n+c)=f(n)+c \text{ } \left(\clubsuit \right)\]Assume $c \leq 1$. $\bullet$ If $c=0$, then $0=c=f(f(0)+1)+1$, which is a contradiction. $\bullet$ If $c=1$, then $f(n+1)=f(n)+1$ will easily give us the only working function is $f(n)=n+1$. Assume $c \geq 2$. See that $f(n) \pmod c$ only depends on $n \pmod c$. Hence we get that \[\{f(0),f(1),\dots,f(c-1)\} \equiv \{0,1,\dots,c-1\} \pmod c\]Again see that $f(n)-n=f(n \pmod c)-n \pmod c$. And hence we get \[K=\sum_{i=0}^{c-1} f(i)-i=\sum_{i=1}^{c-1} f^2(i)-f(i)=\sum_{i=1}^{c-1} f^3(i)-f^2(i)=\sum_{i=1}^{c-1} f^4(i)-f^3(i)\]And so if we sum it up and use $\clubsuit$, we get that $K=\frac{c^2}4$. And see that again since we have \[f(f(n)+1)=n+c-1 \text{ and } \sum_{i=0}^{c-1} f(f(i)+1) \equiv \sum_{i=1}^{c-1} i \pmod c\]We get that \[(c-1)c=\sum_{i=1}^{c-1} f(f(i)+1)-i=K+\sum_{i=1}^{c-1} f(i)-i+1 = 2K+c = \frac{c^2}2+c \iff c=4\]Let $G_f$ be the digraph of $f$ on $\{0,1,2,3\}$ modulo $4$. That is $i \rightarrow j \iff f(i) \equiv j \pmod 4$. One can do a big aah cash bash and see that the only digraph which satisfies $\spadesuit$ is $0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 0$. Again recall that $f^4(0)=4$, check some values and see that the only two working functions are \[\boxed{f(n) \equiv n+1 \text{ } \forall \text{ } n \in \mathbb{Z}_{\geq 0}} \text{ AND } \boxed{f(n)= \begin{cases} n+1 \text{ if } n \equiv 0 \pmod 2 \\ n+5 \text{ if } n \equiv 1 \pmod 4 \\ n-3 \text{ if } n \equiv 3 \pmod 4 \end{cases} \text{ } \forall \text{ } n \in \mathbb{Z}_{\geq 0}}\]