How can I solve the functional equation $ f ( x + 1 ) + 1 = f \big( f ( x ) + 1 \big) $?

Question

Let $ \mathbb N = \{ 0 , 1 , 2 , \dots \} $. Find all the functions $ f : \mathbb N \to \mathbb N $ such that $$ f ( x + 1 ) + 1 = f \big( f ( x ) + 1 \big) $$ for all $ x \in \mathbb N $.

• I noticed, while looking for injectivity, that $$ \forall ( x , y , n ) \in \mathbb N ^ 3 : f ( x ) = f ( y ) \implies f ( x + n ) = f ( y + n ) \text . $$
• Then I found out that $ f ( 0 ) \ne 0 $, because if it's the case, by letting $ x = 1 $ we'll have $$ f ( 1 ) + 1 = f \big( f ( 0 ) + 1 \big) \implies 1 = 0 \text . $$

Is there any method to solve this?

Answer 1

Edit: as noted in the comments, the property only holds for natural numbers, not all real numbers. Assuming that it does hold for real numbers, the following can help.

Let us look at the function with this same property, but on $\mathbb{R}$. Then:

$$\Big[ f(x+1)+1 \Big]' = f'(x) = f'(x) \cdot f'(f(x)+1)$$ by the chain rule.

Therefore:

$$f'(f(x)+1) = 1 \ \ \ \lor \ \ \ f'(x)=0$$ However, the latter would imply that $f(x)$ is constant for all $x$, but this is not the case since for $f(x)=c$ we have $f(x+1)+1=c+1\neq f(f(x)+1) = c$.

By integrating both sides of the first equation, and using the fundamental theorem of calculus we get:

$$f(f(x)+1)-f(f(0)+1)=x$$

from which follows

$$f(x+1)+1-(f(0+1)+1) = x$$

Which ultimately leads to

$$f(x)=x+f(1)-1$$

We now just have to find $f(1)$, which should be $\geq1$ for this to hold. I found that the property holds at least for $f(1)=2$ (so for $f(x)=x+1)$, but I'm not sure if there are more possibilities.

Of course, we can go back to the case where $f$ is a function of natural numbers in the last step, since any property that holds for all real numbers must automatically also hold for the natural numbers amongst them.

Answer 2

Here are some results that I found.

---

First, let $u_n=f(n)$ and $w_n = u_n +1$ we have $$ u_{n+1}+1=f(u_n+1) $$ so $$ w_{n+1}=f(w_n)=\cdots=f^{n+1}(w_0) $$ then $$ f(n)+1=f^n(f(0)+1). $$ If $c=f(0)+1 \ge 2$, we have $$ f(n)=f^n(c)-1. $$ Let's see if we can find some solutions: if $f(n)=n^k$ ($k \ge 2$) we have $f^m(n)=n^{k^m}$ so $n^k=c^{k^n}=\exp(k^n\ln(c))$ but this can't be for large values of $n$ (the RHS explodes very quickly compared to the LHS).

---

If $f$ is bounded by $M \in \Bbb N$ we have $$ f(n) \le M $$ so $$ f(n) \le M-1 $$ So $f=0$, so $f$ isn't bounded.

---

If $\exists x, f(x)=x$ we have $f(x+1)+1=f(x+1)$ so $1=0$, which is absurd.

---

Answer 3

Theorem 1: The unique function $f:\mathbb{N}\to\mathbb{N}$ satisfying $$f(x+1)+1=f(f(x)+1)$$ for all $x\in\mathbb{N}$ is given by $f(x)=x+1$ for all $x\in \mathbb{N}$.

Before we can prove this, we need some Lemmas. The proof of Theorem $1$ can be found at the very bottom of this post.

---

In what follows, let $f:\mathbb{N}\to\mathbb{N}$ be any function satisfying the functional equation.

Lemma 2: Suppose $x,k\in\mathbb{N}$ with $k\ge 1$ and $f(x)=f(x+k)$. Then for all $a,b\in\mathbb{N}$ with $a,b\ge x$ and $a\equiv b\pmod k$, we have $f(a)=f(b)$.

Proof: Note that $$f(x+1)+1=f(f(x)+1)=f(f(x+k)+1)=f(x+k+1)+1,$$ so $f(x+1)=f(x+k+1)$. With induction on $n$ we conclude that $f(x+n)=f(x+k+n)$ for all $n\in\mathbb{N}$.

Now it suffices to prove that $f(x+mk)=f(x)$ for all $m\in\mathbb{N}$. We proceed by induction on $m$. The case $m=0$ is trivial and the case $m=1$ is given. Let $m\ge 1$ and assume the claim is true for all integers $0,\ldots,m-1$. Then $f(x+(m-1)k)=f(x+mk)$, so putting $n=k$ in the previous identity, we find that $$f(x+(m+1)k)=f(x+mk)=f(x).$$ This completes the proof by induction.

We now know that $f(x+mk+n)=f(x+n)$ for all $m,n\in\mathbb{N}$, which is the lemma. $\square$

Corollary 3: If $f$ is not injective, then $f$ is bounded.

Proof: If $f(x)=f(x+k)$ for some $x,k\in\mathbb{N}$ and $k\ge 1$, then for all $y\ge x$, the value of $f(y)$ depends only on $y\pmod k$ by Lemma $2$. Therefore, $f$ only takes finitely many values, and must be bounded. $\square$

Lemma 4: $f$ is unbounded and injective.

Proof: By Corollary $3$, it suffices to show that $f$ is unbounded. Assume for the sake of contradiction that $f$ is bounded. Let $M$ be its maximum and let $y\in\mathbb{N}$ with $f(y)=M$.

If $y\ge 1$, then there exists an $x\in\mathbb{N}$ with $y=x+1$, whence $f(f(x)+1) > f(x+1)=f(y)=M$; a contradiction. Therefore, $f(0)=M$ and $f(y)<M$ for all $y\ge 1$.

Let $M_2$ be the maximum of $f$ on $\mathbb{N}_{\ge 1}$, and let $x\in\mathbb{N}$ with $f(x+1)=M_2$, then $f(f(x)+1)>f(x+1)=M_2$, whence $f(f(x)+1)=M$ and $f(x)+1=0$; a contradiction. $\square$

Lemma 5: For all $x,n\in\mathbb{N}$, we have

• $f\left(f^{\circ n}(x)+1\right)=f(x+1)+n$.
• $f(x+n)+1=f^{\circ n}(f(x)+ 1)$

Proof: Induction on $n$.

Lemma 6 The sequence $0,f(0),f^{\circ2}(0),\ldots$ is a permutation of $\mathbb{N}$, and we have $\operatorname{im}(f)=\mathbb{N}_{\ge 1}$.

Proof: Let $m$ be the minimal value of $f$ on $\mathbb{N}_{\ge 1}$ and let $x_0\in\mathbb{N}$ with $f(x_0+1)=m$. Let $x\in\mathbb{N}$ and write $f(x+1)=f(x_0+1)+n$ for some $n\in\mathbb{N}$, then Lemma $5$ gives $$f(x+1)=f(x_0+1)+1=f\left(f^{\circ n}(x_0)+1\right)$$ By injectivity, $x=f^{\circ n}(x_0)$. Hence $\mathbb{N}\setminus\{x_0\}\subseteq\operatorname{im}(f)$.

Suppose that $x_0=f(y)$ for some $y\in\mathbb{N}$, then $y=f^{\circ k}(x_0)$ for some $k\ge 0$, so $x_0=f^{\circ(k+1)}(x_0)$. This means that $\#\operatorname{im}(f)=k$, which means $f$ is bounded. This contradicts Lemma $4$, so $x_0\not\in\operatorname{im}(f)$. We conclude that $\operatorname{im}(f)=\mathbb{N}\setminus\{x_0\}$.

However, the first identity in Lemma $5$ implies that $\operatorname{im}(f)=\mathbb{N}_{\ge m}\cup \{f(0)\}$. If $x_0=0$ we are done. Otherwise, $m=2$ and $\{0,1\}=\{f(0),x_0\}$. Because $f(0)\neq 0$ it follows that $x_0=0$. $\square$

Corollary 7 For all $k\in\mathbb{N}_{\ge 1}$, the function $f^{\circ k}$ has no fixed points.

---

Proof of Theorem 1: Define a new function $g:\mathbb{N}\to\mathbb{N}$ by $g(n):=f(f(n)+2)$. Now, Lemma $5$ gives that for all $n\in\mathbb{N}$, $$ g(n) = f\left(f(n)+1+1\right) = f\left(f^{\circ n}(f(0)+1)+1\right) = f(f(0)+2)+n=g(0)+n. $$ Next, with Lemma $6$ and some abuse of notation, $$ \mathbb{N}_{\ge g(0)} = g(\mathbb{N}) = f\left(f(\mathbb{N})+2\right) = f(\mathbb{N}_{\ge 3}) = \mathbb{N}_{\ge 1}\setminus\{f(0),f(1),f(2)\}. $$ Hence, $g(0)=4$ and $\{f(0),f(1),f(3)\}=\{1,2,3\}$.

We now prove that $f(0)=1$ and $f(1)=2$. First, if $f(0)=2$, then $4=g(0)=f(f(0)+2)=f(4)$, but $f$ has no fixed points, so $f(0)\neq 2$. Second, if $f(0)=3$, then $f(1)=2$ and $f(2)=1$, because $f$ has no fixed points, but this implies $f^{\circ 2}(1)=1$, even though $f^{\circ 2}$ has no fixed points either. We conclude that $f(0)=1$. Now, if $f(1)\neq 2$, then $f(1)=3$ and $f(2)=2$, which gives a contradiction because $f$ has no fixed points. We conclude that $f(1)=2$.

Finally, assume that the set $S:=\{x\in\mathbb{N}:f(x)\neq x+1\}$ is non-empty. Let $x\in S$ be minimal, then $x\ge 2$. By Lemma $6$, there exists some $y\in \mathbb{N}$ with $f(y)=x+1$. Now, note that $$ f(y) = f(x-1)+1 = f(f(x-2)+1), $$ so $y=f(x-2)+1=(x-2)+1+1=x$, by injectivity. This is a contradiction, so we conclude that $S$ is empty. Q.E.D.