Two equations with integer functions

Find all functions $f\colon \mathbb{N}\longrightarrow\mathbb{N}$ such that $f(f(x))=x+1$ for all natural integer $x$ .
Same question with $f(f(x))=x+2$ .

I solved itMark it done Add to my listKeep it in your list

I like this problem2 likes

Liked by

Solutions

Reveal solutionsAre you sure? Give it a try first.

Solution by Anduril

Discussions1 useful vote

Let’s assume such a function exists. We have $f(f(x))=x+1\,\,(E)$ .
By applying $f$ to this equation we get : $f^3(x)=f(x+1)$ .
Also, by replacing $x$ with $f(x)$ in $(E)$ : $f^3(x)=f(x)+1$ . Hence, with $a:= f(0)$ , one gets $f(x)=x+a$ and $f(f(x))=x+2a$ . With the hypothesis : $x+1 =f(f(x)) = x+2a$ so $2a=1$ but $a$ is an integer. That is a contradiction.
With a similar reasoning, a solution would satisfy : $f(x+2)=f(x)+2$ . So with $g(x):=f(2x)$ , we have $g(x+1)=g(x)+2$ and so $g(x)=2x+a$ where $a:=f(0)$ .

Symmetrically we have : $f(2x)=2x+a$ and $f(2x+1)=2x+1+b$ where $b:=f(1)-1$ .

Hence, using the original relation $f(f(x))=x+2$ one gets:

$\hookrightarrow$ If $a$ is even, say $a=2k$ : $2(x+k)+a= f(2x+2k)= f(f(2x)) = 2x + 2$ so $a = 1$ , which is absurd.

$\hookrightarrow$ So $a$ is odd, say $a=2k+1$ : $2x + 2k+1 + b= f(2x+2k+1)=f(f(2x)) = 2x + 2$ so $a+b = 2$ .
But since $a$ is an odd non-negative integer and $b=f(1)-1$ is greater than $-1$ , one gets either $a=b=1$ or $a=3$ and $b=-1$ .

Finally, this leads to two possible functions: $f_1\colon x\mapsto x+1$ and $f_2$ such that $f_2(2x):=2x+3$ and $f_2(2x+1)=2x$ for all $x\in\N$ .

Reciprocally, a quick check implies that these functions are indeed solutions of our problem, which concludes.

Report