Find all functions f such that $f(f(x))=f(x)+x$

Let $f:\mathbb{R}\to\mathbb{R}$ be a function such that $f(f(x))=f(x)+x, \forall x\in\mathbb{R}$. Find all such functions $f$.

Clearly, $f$ is an "one-to-one function". I have tried setting where $x\rightarrow f(x)$ so: $f(f(f(x)))=f(f(x))+f(x)=2f(x)+x$.

Also, from the original relation, we get that: $f(f(f(x)))=f(f(x)+x)$.

Equating the RHS of the last two relations we get that: $f(f(x)+x)=2f(x)+x$.

Probably to exploit the 1-1 we need a relation of the form $f(f(x))=f(\cdots)$.

I don't know how to carry this further... Any hint?

Solution 1:

Claim: $f(0)=0$.

Assume $f(0) = k\neq 0 $, then $f(k)=f(k)+k$, a contradiction.

Claim: If $f(x)$ is an analytic function, $f(x)=\phi x$ or $f(x)=-x/\phi$.

If $f$ is an analytic function, it has a unique polynomial expansion with zero constant term, i.e. $f(x) = a_1x+a_2x^2 +\cdots$. Then by comparing powers we get that: $$a_1=\phi, -1/\phi$$ And all other powers are zero.

If $f(x)$ is not analytic, I'm not sure what else can be said about it.

Solution 2:

For each number $x\in[1,\phi)$, let either $$f(x)=\phi x,f(-x)=-\phi x\text{ or else }\\f(x)=-x/\phi,f(-x)=x/\phi$$ The choice is independent for each $x$ in that interval. Then, for all other numbers, $f(x\phi^k)=f(x)\phi^k$.
For each ladder $x\phi^{-2},x\phi^{-1},x,x\phi,x\phi^2,...$, $f$ consistently shifts numbers up the scale, or down the scale.

Solution 3:

Suppose $f$ is continuous and bijective... I claim either $f(x) = \phi x$ for all $x$, or $f(x) =-x/\phi$ for all $x$. Here $\phi=(1+\sqrt{5})/2$.

We use the Fibonacci numbers $F_n$: $$ F_{n+2}=F_{n+1}+F_n,\qquad F_0=0,\qquad F_1=1 . \tag{1}$$ With $F_{-n}=(-1)^{n+1}F_n$, the recurrence holds for all integers, positive and negative. And of course $$ F_n = \frac{\phi^n+(-\phi)^{-n}}{\sqrt{5}} \tag{2}$$

We assume $f$ is continuous and bijective. And satisfies $$ f(f(x)) = f(x) + x \tag{3}$$ Proved in another answer: $f(0)=0$. So $f$ is either increasing or decreasing. Let's consider the increasing case. So $f$ sends positive to positive and negative to negative. I claim $f(x) = \phi x$ for all $x$. Let $a > 0$, $f(a)=b$. (The case $a<0$ is below.) We will show $b = \phi a$.

Starting with $f(a)=b$, we get by induction using (1) and (3): $$ f(F_{k-1}a+F_{k}b)=F_{k}a+F_{k+1}b \tag{4}$$ for all $k \ge 0$. And applying (1), (3) backward, we get (4) for negative $k$ also. (We assumed $f$ is bijective, so we can go backward in (3).)

Since this is the increasing case, we have $b=f(a)>0$ since $a>0$. For $k>0$ consider the negative values $-k$: $$ f(F_{-k-1}a+F_{-k}b)=F_{-k}a+F_{-k+1}b \\ f\big((-1)^kF_{k+1}a+(-1)^{k+1}F_{k}b\big) =(-1)^{k+1}F_{k}a+(-1)^kF_{k-1}b $$ What is the sign of $v_{-k}=(-1)^kF_{k+1}a+(-1)^{k+1}F_{k}b$ ? If $b/a > \phi$,then by (2) the sign is $(-1)^{k+1}$ for large $k$. So $f$ sends positive to negative and negative to positive for these values $v_{-k}$. Similarly, if $b/a<\phi$, then the sign of $v_{-k}$ is $(-1)^k$ for large $k$, and again $f$ sends positive to negative and negative to positive for these values $v_{-k}$. Since this is impossible, we conclude $b/a=\phi$.

For case $a<0$, we have $b<0$. Again we get negative to positive and positive to negative for $v_{-k}$ with $k$ large.

Now consider the decreasing case. I claim $f(x) = -x/\phi$ for all $x$. We still get (4). But now $f$ is supposed to send positive to negative and negative to positive. This time we get our contradictions by considering $v_k$ for large positive $k$ in (4).