Find all functions $f :\mathbb{N_0} \to \mathbb{N_0}$ such that $f(f(n)) = n + k$ for any $n \in \mathbb{N_0}$ and $k$ is a positive integer.

Question

Problem

Let $k$ be a positive integer. Find all functions $f :\mathbb{N_0} \to \mathbb{N_0}$ such that $$f(f(n)) = n + k$$ for any $n \in \mathbb{N_0}$.

My approach

I tried substitution. Here is what I got: $$f(f(n+1))-f(f(n))=1 \tag{1}$$ $$f(n+k)=f(f(f(n)))=f(n)+k \tag{2}$$ However, I don't know how to use them to proceed further.
As suggested in the comments, here is what I got for $k=1$ and $k=2$.
For $k=1$,
Using $(2)$ we have $$f(n+1)=f(n)+1$$ Now let $f(0)=c$ such that $c \in \mathbb{N_0}$. Then, we have $f(n)=n+c$. Then $$f(f(n))=n+2c=n+1$$ which is a contradiction and this leads there is no solution for $k=1$.
For $k=2$, similar works lead that $f(n)=n+1$ is the only solution.

---

So, I need a generalized solution to the problem.

Answer 1

(Disclaimer: It's late, so I might have made an error here. However, I believe this is correct.)

Hint / Steps: (If you're stuck, show what you've tried.)

• OP showed that $f(n+ k) = f(n) + k$.
• Hence, the function is uniquely defined by $ f(0), f(1), \ldots f(k-1)$.

Let $ a_k$ denote $ a \mod{k}$.
Let $ [k] = \{0, 1, \ldots, k-1\}$.

• Show that if $ f(a_k ) = b_k$, then 1) $a_k \neq b_k$ and 2) $f(b_k) = a_k$. Hence, we can pair up these residues.
• Hence if $ k$ is odd, then there are no solutions.
• Show that if $ a, b \in [k] $ such that $f(a_k) = b_k$, then either $f(a) = b, f(b) = a+k$ or $f(a) = b+k, f(b) = a$.
• Hence, if $k$ is even, show that there are $\frac{ k!}{ (k/2)!}$ solutions. Describe all of them.