$f: \mathbb{N}\cup\{0\} \longrightarrow \mathbb{N}\cup\{0\}, \forall x\in\mathbb{N}\cup\{0\}, f(x+1)+1 = f(f(x) + 1)$

Question

I try to solve this question : Find all function $f:\mathbb{N}\cup\{0\}\longrightarrow \mathbb{N}\cup\{0\}$ such that $\forall x\in\mathbb{N}\cup\{0\}, f(x+1)+1 = f(f(x)+1)$.

My attempt : By induction, we obtain $$\tag1\forall x, k\in\mathbb{N}\cup\{0\}, f(x+k)+1 = f^{x}(f(k)+1)$$ and $$\tag2\forall k\in\mathbb{N}\cup\{0\}, f(x+1)+k = f(f^{k}(x)+1).$$

Since $\forall x\in\mathbb{N}\cup\{0\}, f(x+1)+1 = f(f(x)+1)$, if $f(x) = f(y)$ then $f(x+1) = f(y+1)$. From $(2)$, we know the image of $f$ is infinite. So $f$ is injective.

From $(2)$, we have $f(f^{k}(f(x)+1)+1) = f(f(x)+2)+k$. From $(1)$, we also have $f(f^{k}(f(x)+1)+1) = f(f^{x+k}(f(0)+1)+1)$ then form $(2)$, $f(f^{x+k}(f(0)+1)+1) = f(f(0)+2)+x+k$. So we have $$\tag3\forall x, k\in\mathbb{N}\cup\{0\}, f(f(x)+2)+k = f(f(0)+2)+x+k.$$

From $(3)$, we have $$\tag4\forall x\in\mathbb{N}\cup\{0\}, f(f(x)+2) = x + f(f(0)+2).$$ Substitute $f(x)+2$ for $x$ in $(4)$, we have $$\tag5\forall x\in\mathbb{N}\cup\{0\}, f(x+m) = f(x)+m,$$ where $m = f(f(0)+2)+2$.

Since $f$ is injective, if $m|f(x)-f(y)$, then $f(x)-f(y) = x-y$.

This question is from concours SMF junior 2020 https://smf.emath.fr/evenements-smf/annonce-concours-smf-junior-2020

Answer 1

Some random thoughts ...

---

From your finding $(5)$, we see that for $m:=f(f(0)+2)+2$, the map $g\colon \Bbb Z/m\Bbb Z\to \Bbb Z/m\Bbb Z$, $x+m\Bbb Z\mapsto f(x)+m\Bbb Z$ is well-defined and obeys $$g(x+1)+1=g(g(x)+1) $$ and is bijective. In other words, $g$ is a permutation of the $m$ residue classes. This permutation must be a single $m$-cycle, for if there is some $x\in\Bbb Z/m\Bbb Z$ and $0<k<m$ with $g^{k}(x)=x$, then by the modulo version of $(2)$, $g(x+1)+k=g(g^{k}(x)+1)=g(x+1)$, contradiction.

Moreover, $f(0),\ldots, f(m-1)$ are the smallest representatives in $\operatorname{im}(f)$ of their respective residue class modulo $m$. In particular, if $f(0)\ge m-2$, we find that $m-2=f(f(0)+2)=m+f(f(0)+2-m)\ge m$, contradiction. Hence $$\tag6 m\ge f(0)+3\ge4.$$

If $f(x)\ge m-1$, then $$ f(x+1)=f(f(x)+1)-1=f(f(x)+1-m)+m-1\ge m-1.$$ If $x\ne f(0)+2$ and $f(x)\ge m-2$, then $f(x)\ne f(f(0)+2)=m-2$ and so the previous applies, i.e., $f(x+1)\ge m-1$. It follows that $f(x)<m-2$ for $x<f(0)+2$, and $f(x)\ge m-1$ for $x>f(0)+2$. In particular, by injectivity $$\tag7m\ge f(0)+4\ge 5.$$

If $a\in\operatorname{im}(f)$ then either $a=f(0)$ or $a+1\in\operatorname{im}(f)$ because $a=f(x+1)$ implies $a+1=f(f(x)+1)$. Hence $\operatorname{im}(f)$ is either of the form $[n,\infty)$ or of the form $[n_1,f(0)]\cup [n_2,\infty)$ with $n_1+m>n_2$.

Assume $\operatorname{im}(f)=[n,\infty)$. By $(7)$, $n\le m-4$. We know that $\{f(0),\ldots,f(m-1)\}=\{n,\ldots, n+m-1\}$. Of the $m$ numbers $f(r)$, $0\le r<m$, exactly $n+1$ must be $\ge m-1$. By the results above, these $n+1$ numbers must be $f(0)+3,\ldots, m$. Thus $$n=m-f(0)-3.$$ As $n\ge f(0)$, this makes $$m\ge 2f(0)+3.$$