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.
Best Answer
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.