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.

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}. $$