Solutions to the functional equation $f(f(x))=f(x+1)$

Question

I am trying to find all solutions to $f(f(x))=f(x+1)$ with $f:\mathbb{R}\rightarrow \mathbb{R}$.

I have found that $f(x)=x+1$ is a solution and $f(x)=c$ for any $c \in \mathbb{R}$ and I think that there are no other rational (polynomial) solutions.

Are there any other (perhaps non-continuous) solutions?

Answer 1

There are no other polynomial solutions - if $f$ has degree $n$, then $f(f(x))$ has degree $n^2$, which is greater than $n$ if $n > 1$. And if $f$ has degree of at most $1$, then $f(x) = ax + b$, and we can find that solutions are only $a = 0$ and $a = 1, b = 1$ - which corresponds to $f(x) = c$ and $f(x) = x + 1$.

There are many discontinuous solutions even without AC. For example, $$f(x) = \begin{cases}0,\ x \in \mathbb{Z}\\ \frac{1}{2}, x \notin \mathbb{Z} \end{cases}$$.

There are also some other continuous solution. For example, $f(x + n) = |x|$ where $n \in \mathbb{Z}$ and $-\frac{1}{2} \leq x < \frac{1}{2}$ (any number has unique such representation): $f(f(x + n)) = f(x) = x$ and $f(x + n + 1) = x$. Alternative form of the same function: $f(x) = \rho(x, \mathbb Z) = \min\limits_{n \in \mathbb Z} |x - n|$.

Answer 2

There are in fact uncountably many non-continuous solutions:

You can take $f: \mathbb{R} \rightarrow \mathbb{R}$ with $f(x)=0$, if $x \in \mathbb{Q}$, and $f(x)=y$, if $x \notin \mathbb{Q}$, for every irrational number $y \in \mathbb{R}$.

This works since there are uncountably many irrational numbers and the sum of an irrational number with a rational number is irrational.

Answer 3

There are an infinite number of non-continuous solutions which can be created by combining the two solutions you gave. For example, define $A_k$ as the set of algebraic numbers of degree $k$ or less. That is, $A_k$ is the set of algebraic numbers whose minimal polynomial has degree $k$ or less. Now, if $\alpha\in A_k$ then $\alpha+1\in A_k$ and if $\alpha\not\in A_k$ then $\alpha+1\not\in A_k$. Now, define

$$f(x)=\begin{cases} x+1 & x\in A_k \\ c & x \in \mathbb{R}/A_k \end{cases}$$

(for any constant $c$). For any particular $x$ we have

$$f(x)\in A_k \Leftrightarrow x\in A_k$$

Thus, $f(x)$ satisfies the functional equation.