Find all strictly increasing functions on positive integers such that $f(f(n))=n+2$

Question

This is a very interesting word problem that I came across in an old textbook of mine. So I know its got something to do with induction, which yields the shortest, simplest proofs for proving the finite amount of functions, but other than that, the textbook gave no hints really and I'm really not sure about how to approach it. Any guidance hints or help would be truly greatly appreciated. Thanks in advance :) So anyway, here the problem goes:

Let $\mathbb{N}^+$ denote the set of positive integers. Find all functions $f:\mathbb{N}^+ \rightarrow \mathbb{N}^+$ which are strictly increasing and such that for all positive integers $n$, we have $f(f((n))=n+2.$

So I found the function $f(n)=n+1$ works, but I'm not sure if it is the only possibility, and even so, how to prove that it is the only solution.

Answer 1

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.

Answer 2

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.

Answer 3

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