Find all functions of positive integers for $f(f(n))=n+2$

Lemma: $f(k)>k$.

Pf: it is clear that $f(1)≥1$ and that $f(1)\neq 1$ so the claim is true for $k=1$. Inductively suppose it is true up to $k-1$. Then $f(k-1)>k-1$ so $f(k-1)≥k$. Since $f(k)>f(k-1)$ we are done.

Claim: $f(n)=n+1$

Pf: Indeed the Lemma shows that $f(n)≥n+1$. But $f(f(n))=n+2\implies f(n)≤n+1$ and we are done.


Note that $f(f(1))=3$ and $f(1)\ge 1$

We can't have $f(1)=1$ because that would make $3=f(f(1))=f(1)=1$

If we had $f(1)=3$, we'd have $3=f(f(1))=f(3)$, but $f$ is strictly increasing, so this is a contradiction. As would be if $f(1)=n\gt 3$ when we'd have $3=f(f(1))=f(n)\gt f(1)\gt 3$.

So we have $f(1)=2$, and then $f(2)=f(f(1))=3$ and if $f(r)=r+1$ we have $r+2=f(f(r))=f(r+1)$, and you can prove by induction.


It's quite clear that $f$ cannot fixed a point $k$, i.e. $f(k) \neq k$ for every $k > 0$. Moreover, because $f$ is strictly increasing, we have $f(k) > k$. Therefore, one can write $f(k) = k + r_k$ with $r_k > 0$. Then, given any $k$, we have:

\begin{align*} k + r_k + r_{k + r_k} = f(k + r_k) = k + 2 \end{align*}

Which means that: $r_k + r_{k +r_k} = 2$, yielding that $r_k = 1$ for every $k$.