Solving f(f(n)) = n + 2 on the positive integers

Step 1: a recursion. Apply $f$ to $f(f(n))=n+2$ and use the equation with $n$ replaced by $f(n)$:
$$f(n+2)=f\bigl(f(f(n))\bigr)=f(n)+2.$$
Let $a=f(1)$ and $b=f(2)$. Then for $k\ge1$:
$$f(2k+1)=a+2k,\qquad f(2k)=b+2k-2.$$

Step 2: using the equation at $n=1$. $f(a)=3$.
- If $a$ is odd, $a=2m+1$, then $f(a)=a+2m=2a-1$; setting this equal to $3$ gives $a=2$, which is not odd. Contradiction.
- So $a$ is even, $a=2m$, and $f(a)=b+a-2=3$ gives $b=5-a\ge1$, so $a\in\{2,4\}$.

Step 3: two candidates.
- $a=2$, $b=3$: $f(2k+1)=2k+2$ and $f(2k)=2k+1$, i.e. $f(n)=n+1$.
- $a=4$, $b=1$: $f(2k+1)=2k+4$ and $f(2k)=2k-1$, i.e. $f(n)=n+3$ for odd $n$ and $f(n)=n-1$ for even $n$.

Step 4: verification. For $f(n)=n+1$: $f(f(n))=n+2$. For the second function, if $n$ is odd then $f(n)=n+3$ is even, so $f(f(n))=n+3-1=n+2$; if $n$ is even then $f(n)=n-1$ is odd (and $\ge1$), so $f(f(n))=n-1+3=n+2$.

Answer. Exactly two functions: $f(n)=n+1$, and $f(n)=n+3$ for odd $n$, $f(n)=n-1$ for even $n$.

Lesson. Reduce $f(f(n))=g(n)$ to a recursion by applying $f$ again, then use the small values to pin down the free parameters, and always check whether more than one solution survives.