How can I attempt this FE

Question

Prove that there is no function f : ℕ→ℕ such that f (f (n)) = n + 1. Here ℕ is the positive integers {1, 2, 3,...}.

I have messed around with the FE but can't seem to produce anything meaningful. I found the solution online which states but I'm having trouble following the part where it states that the former yields f 2 (N):

Let M = {2,3,...} = N\ {1}. Then f 2 (N) = M and therefore f(N) = N or M. The former yields f 2 (N) = N, which is not the case, so we must have the latter which yields f(M) = M. It follows that f 2 (M) = M and we have a contradiction, so there is no such f , as required.

Link is added below:

https://www.math.vt.edu/people/plinnell/Vtregional/E18/index.html

Answer 1

Note that \begin{align*} 1 \mapsto k_1 &\mapsto 2\\ 2 \mapsto k_2 &\mapsto 3\\ 3 \mapsto k_3 &\mapsto 4\\ \vdots \mapsto \vdots &\mapsto\vdots\\ r \mapsto k_r &\mapsto r+1\\ \vdots \mapsto \vdots &\mapsto\vdots\\ \end{align*} As you can see from the composition mapping, $M=\{2,3,4,5, \ldots\}$ is definitely in the range of $f$. So $M \subseteq f(\Bbb{N})$.

Question: is $1 \in f(\Bbb{N})$?

Note that from the second part of the composition, it is clear that $1 \not\in f(\Bbb{N})$. Thus the range $f(\Bbb{N})=M$.

This means for all $i$, $k_i \in M$. Said differently $f(M)=M$. But then $f(f(M))=M$. If this was true then how will $2$ be in the range of $f$?

Answer 2

Since $f(n+1)= (f \circ (f \circ f))(n)=((f \circ f) \circ f)(n)= f(n)+1,$ we have $f(n)=n+c$ where $c=f(1)-1 \in \mathbb{Z}.$ But then $c=1/2$ by substitution, a contradiction.