Olympiad-style question about functions satisfying condition $f(f(f(n))) = f(n+1) + 1$ QN: What functions (from non-negative integers to non-negative integers) satisfy the condition
$$f(f(f(n))) = f(n+1) + 1$$
Comment: Evidently $f(n) = n+ 1$ is one solution. Equally evidently no other polynomial will work. But there, having played around for a while, I get stuck.
There's a story behind the question, which makes me as interested in the question whether there is a systematic way of tackling questions like this, as in the question of what the answer is.
 A: Let $m=f(n+1)$, apply $f(\cdot)+1$ to both sides:
$$\begin{align} f\bigl(\,f(f(f(n)\,\bigr)+1&=f\bigl(\,f(n+1)+1\,\bigr)+1\\
&= f(m+1)+1\\
& = f(f(f(m)))\\
&=f(f(f(f(n+1)))),\end{align}$$
so with $g:=f^{\circ 4}\colon \Bbb N_0\to\Bbb N_0$, we have
$$ g(n+1)=g(n)+1,$$
and by induction
$$ g(n)=\underbrace{g(0)}_{=:c}+n.$$
Then $$f(n+c)=f(g(n))=g(f(n))=f(n)+c. $$
In particular, $g$ (and with it, $f$) is injective.
As $f^{\circ 3}(n)\ne 0$ for all $n$, $f$ and $g$ cannot be onto, hence $c>0$.
We note that this implies
$$\tag1 f^{\circ k}(n)\ne n\quad \text{if }k>0$$
as otherwise $n=f^{\circ 4k}(n)=g^{\circ k}(n)=n+kc\ne n$, contradiction.
Let $S_0=\Bbb N_0\setminus f[\Bbb N_0]$ be the points missing from the image of $f$ and $S_n=f ^{\circ n}[S_0]$. Then the $S_n$ are pairwise disjoint and $f$ induces bijections $S_n\to S_{n+1}$. As
$$\{0,\ldots, c-1\}=\Bbb N_0\setminus g[\Bbb N_0]=S_0\cup S_1\cup S_2\cup S_3,$$
we see that $c=4|S_0|$.
If $x\in (S_0\cup S_1\cup S_2)\setminus\{0,f^{-1}(c-1)\}$, then $f(x)\in (S_1\cup S_2\cup S_3)\setminus\{c-1\}$, so $f^{\circ 3}(x-1)=f(x)+1<c$ and finally $x-1\in S_0$.
We conclude that $$\tag23|S_0|-2\le \left|(S_0\cup S_1\cup S_2)\setminus\{0,f^{-1}(c-1)\}\right|\le |S_0|,$$ so $|S_0|\le 1$.
As $c>0$, we conclude $|S_0|=1$ and $c=4$.
We can write $S_n=\{a_n\}$ and thus $(a_0,a_1,a_2,a_3)$ is a permutation of $(0,1,2,3)$, and $f$ maps
$$ a_0\mapsto a_1\mapsto a_2\mapsto a_3\mapsto a_0+4\mapsto a_1+4\mapsto a_2+4\mapsto a_3+4\mapsto a_0+8\mapsto \cdots$$
By sharpness of inequality $(2)$, $0$ and $f^{-1}(3)$ are distinct elements of $S_0\cup S_1\cup S_2$ (and $f^{-1}(3)$ exists in the first place!), so one of $a_0,a_1,a_2$ is $0$, one of $a_1,a_2,a_3$ is $3$, and $f(0)\ne 3$.
So $f(0)=1$ or $f(0)=2$. If $f(0)=2$, then $4=g(0)=f(f(f(2)))=f(3)+1$, contradicting $(1)$. Therefore $f(0)=1$.
This leaves us with $(a_0,a_1a_2,a_3)$ one of
$$ (0,1,2,3), (0,1,3,2), (2,0,1,3), (2,3,0,1).$$
The first case leads to the solution
$$\tag A f(n)=n+1. $$
The second case leads to $2=f(f(f(0)))=f(1)+1=4$, contradiction.
The third case leads to $3=f(f(f(2)))=f(3)+1=7$, contradiction.
The fourth case leads to the valid solution
$$\tag B f(n)=\begin{cases}n+2&n\equiv 0,1\pmod 4\\n-2&n\equiv 2,3\pmod 4\end{cases}. $$
