# If $f(f(x)) = x+1, f(x+1) = f(x) + 1$, is it true that $f(x) = x + 1/2$

calculusfunctional-equationsiterated-function-system

If $$f(f(x)) = x+1, f(x+1) = f(x) + 1$$, where $$f: \Bbb R \rightarrow \Bbb R$$ is real-analytic, bijective, monotonically increasing, is it true that $$f(x) = x + 1/2$$?

I have tried to represent $$f(x)$$ as power series in a neighborhood of arbitrary $$x_{0}$$ and $$y_{0} = f(x_{0})$$. It's obvious that we can choose such a neighborhood $$U_{0}(x_{0})$$ that it's image by $$f$$ is $$U_{1}(y_{0})$$. Then, we can try to find the power series of $$f(f(x))$$, which is equal to $$x+1$$. But I cannot see, how such an equation shows that $$f(x) = x + 1/2$$.

The answer is no. All that can be said is that $$f$$ is conjugate to the shift $$x\mapsto x+1/2$$. More precisely:
Theorem A real analytic function $$\newcommand{\R}{{\mathbb R}}f:\R\to\R$$ satisfies $$f(f(x))=x+1$$ for all real $$x$$ if and only if it can be written $$\tag{1}f(x)=h\left(h^{-1}(x)+\tfrac12\right)$$ where $$h:\R\to\R$$ is real analytic and satisfies $$h(x+1)=h(x)+1$$ and $$h'(x)>0$$ for all real $$x$$.
Remarks: 1. (1) is equivalent to $$h^{-1}\circ f\circ h(x)=x+\frac12$$, that is $$h$$ conjugates $$f$$ to the shift $$x\mapsto x+\frac12$$.
2. The Theorem is also valid for continuous functions instead of real analytic functions. The statement "$$h'(x)>0$$" has to be replaced by "$$h$$ strictly increasing".
3. An analogous theorem holds for real analytic $$f$$ satisfying $$f^{\circ n}(x)=x+1$$ where $$f^{\circ n}$$ denotes the repeated composition of $$n$$ copies of $$f$$.
Proof: The sufficieny of (1) had already been checked in previous answers or comments: $$f(f(x))=h(h^{-1}(x)+1)=h(h^{-1}(x))+1=x+1.$$ So let us prove the necessity as well. Recall from the comments to the question that $$f(x+1)=f(x)+1$$ for all $$x$$ because both expressions are equal to $$f(f(f(x)))$$ and that $$f$$ is necessarily bijective with inverse $$f^{-1}(x)=f(x-1)=f(x)-1$$. Since $$f$$ is continuous and bijective, it is also strictly monotonous. As $$f(x+1)=f(x)+1$$, it must be strictly increasing.

In order to motivate the construction, let us discuss the uniqueness of $$h$$ in (1), if it exists. We claim that $$\tilde h=h\circ \phi$$ with a strictly increasing real analytic $$\phi:\R\to\R$$ satisfying $$\phi(x+\frac12)=\phi(x)+\frac12$$ works as well as $$h$$. Indeed $$\tilde h(\tilde h^{-1}(x)+\tfrac12)=h(\phi(\tilde h^{-1}(x)+\tfrac12))=h(\phi(\tilde h^{-1}(x))+\tfrac12)=h(h^{-1}(x)+\tfrac12).$$ As $$g(x)=h(x)-1$$ is 1-periodic, it can be written $$g(x)=u(x)+v(x)$$ where $$u(x)=(g(x+\frac12)+g(x))/2$$ is $$1/2$$-periodic and $$v(x)=(g(x)-g(x+\frac12))/2$$ satisfies $$v(x+\frac12)=-v(x)$$. Hence $$h=\psi+v$$, where $$\psi(x)=x+u(x)$$ satisfies $$\psi(x+\frac12)=\psi(x)+\frac12$$. Observe that $$\psi(x)=(h(x)+h(x+\frac12))/2$$ also has a positive derivative and hence an inverse function $$\psi^{-1}$$. Going over to $$\tilde h=h\circ \psi^{-1}$$, we arrive at some $$\tilde h$$ also working in (1) but such that $$\tilde v(x)=\tilde h(x)-x=v\circ \psi^{-1}(x)$$ satisfies $$\tilde v(x+\frac12)=-\tilde v(x)$$.
In summary: If some $$h$$ with (1) exists then there also exists an $$h$$ satisfying additionally $$h(x)=x+v(x)$$ where $$v(x+\frac12)=-v(x)$$.

Now let a real analytic function $$f:\R\to\R$$ satisfying $$f(f(x))=x+1$$ be given. We are looking for some $$h(x)=x+v(x)$$ with $$v(x+\frac12)=-v(x)$$ satisfying $$f(h(x))=h(x+\frac12)$$ or equivalently $$f(x+v(x))=x+\frac12-v(x)$$ or, with $$F(x)=x+f(x)$$, $$F(x+v(x))=2x+\tfrac12.$$ This motivates our definition $$h(x)=x+v(x)=F^{-1}\left(2x+\tfrac12\right).$$ This is well defined because $$F'(x)\geq1$$ and it is well known that it defines a real analytic function. We find $$h'(x)=2/F'(h(x))>0$$ and, via $$F(x+v(x))=2x+\frac12$$, we obtain that $$\tag{2}f(x+v(x))=x+\tfrac12-v(x)\mbox{ for all }x.$$ We claim that $$v(x+\frac12)=-v(x)$$ which shows that $$f(h(x))=h(x+\frac12)$$ and $$v$$ is 1-periodic and thus completes the proof.
For a proof of the claim, (2) implies that $$x+v(x)+1=f(f(x+v(x))=f(x+\frac12-v(x))$$ and therefore, replacing $$x$$ by $$x+\frac12$$, we find $$x+\tfrac32+v(x+\tfrac12)=f(x+1-v(x+\tfrac12))$$and thus, using $$f(x+1)=f(x)+1$$, $$x+\tfrac12+v(x+\tfrac12)=f(x-v(x+\tfrac12)).$$ Hence $$F(x-v(x+\frac12))=2x+\frac12=F(x+v(x))$$ which implies $$-v(x+\frac12)=v(x)$$ as wanted.