# 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?

• @Tintarn Proof for 1-1: Let $x_1,x_2\in\mathbb{R}$ such that $f(x_1)=f(x_2)$. Then, $f(f(x_1))=f(f(x_2))\Rightarrow f(x_1)+x_1=f(x_2)+x_2\Rightarrow x_1=x_2$. Since for all $x_1,x_2\in\mathbb{R}$ we have that: $f(x_1)=f(x_2)\Leftrightarrow x_1=x_2$, f is one-to-one. – Jason Aug 28 '15 at 11:40
• I don't think that the given condition is enough to provide only "nice" solutions. But clearly, $f(x)=\varphi x$ and $f(x)=-\frac{1}{\varphi}x$ are solutions. – Redundant Aunt Aug 28 '15 at 11:47
• @Tintarn Here it is said that a "one-to-one function" is injective. Anyway, I clarified the Original Post. – Jason Aug 28 '15 at 11:48
• @Tintarn Isn't the normal terminology that "one-to-one" implies injectivity and "onto" implies surjectivity? – Daniel R Aug 28 '15 at 12:12
• @Tintarn: See this question, for example. – Cameron Buie Aug 28 '15 at 12:17

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).

• Pfft, continuous is lame. ;) – Hagen von Eitzen Aug 28 '15 at 17:10
• There's no need to assume surjectivity. Injectivity follows readily and your $(4)$ for $a,b>0$ shows (using continuity) that $[0,\infty)$ is in the image. As $x\mapsto-f(-x)$ also has the given property, we conclude that also $(-\infty,0]$ is in the image. (This also shows we need only consider $a>0$) – Hagen von Eitzen Aug 28 '15 at 17:32
• OK, how to prove surjective in the decreasing case? – GEdgar Aug 28 '15 at 20:58

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.

• Great thought! Can you elaborate on "comparing powers"? – Jason Aug 28 '15 at 12:57
• @Jason - Just write out $f=a_0 + a_1 x + a_2 x^2 + \ldots$, and compare powers of $f(f(x)-f(x)-x=0$ which all should be zero. – nbubis Aug 28 '15 at 13:06
• If $f(0)=k,$ then $f(f(0))=f(k)=f(0)+0=k$. How did you get your first line? This implies $f(0)=f(k)$ or $k=0$ by injectivity. – snulty Aug 29 '15 at 12:22
• Knowing that f is continuous and bijective thus monotone, can we prove that f is analytic? – Jason Sep 7 '15 at 9:24

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.

• That is not all the functions, correct? – nbubis Aug 28 '15 at 13:48
• I don't know. There may be a way to define $f(x)$ arbitrarily over an interval, then use the function definition to extend it over $\mathbb{R}$. – Empy2 Aug 28 '15 at 13:51
• Is there another way to break the reals into disjoint sequences $a_k\phi^n+b_k(-\phi)^{-n}$? – Empy2 Aug 28 '15 at 14:11

Pick a Hamel basis $(v_i)_{i\in I}$ for $\mathbb R$ over $\mathbb Q$. Group the basis vectors in pairs $(v_i,v_j)$ and on $v_i\mathbb Q+v_j\mathbb Q$ let $f$ be given (with respect to the basis $(v_1,v_2)$) by the matrix $A=\begin{pmatrix}0&1\\1&1\end{pmatrix}$. As $A^2=A+1$, $f$ has the desired property. In other words: Find $J\subset I$ with $|J|=|I\setminus J|$ and a bijection $h\colon J\to I\setminus J$ and then let $f(\sum_{i\in I} q_iv_i)=\sum_{i\in J}((q_i+q_{h(i)})v_{h(i)}+q_{h(i)}v_i)$ (those are sums, not series!)

• These should be all $\mathbb Q$-linear solutions. My solution set overlaps with @Michael's, but neither solution set is contained in the other. – Hagen von Eitzen Aug 28 '15 at 14:45