# Solving (quadratic) equations of iterated functions, such as $f(f(x))=f(x)+x$

In this thread, the question was to find a $f: \mathbb{R} \to \mathbb{R}$ such that

$$f(f(x)) = f(x) + x$$

(which was revealed in the comments to be solved by $f(x) = \varphi x$ where $\varphi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$).

Having read about iterated functions shortly before though, I came up with this train of thought:

$$f(f(x)) = f(x) + x$$ $$\Leftrightarrow f^2 = f^1 + f^0$$ $$f^2 - f - f^0 = 0$$

where $f^n$ denotes the $n$'th iterate of $f$.

Now I solved the resulting quadratic equation much as I did with plain numbers

$$f = \frac{1}{2} \pm \sqrt{\frac{1}{4} + 1}$$ $$f = \frac{1 \pm \sqrt{1+4}}{2} = \frac{1 \pm \sqrt{5}}{2}\cdot f^0$$

And finally the solution $$f(x) = \frac{1 \pm \sqrt{5}}{2} x .$$

Now my question is: Is it somehow allowed to work with functions in that way?* I know that in the above, there are denotational ambiguities as $1$ is actually treated as $f^0 = id$ ... But since the result is correct, there seems to be some correct thing in this approach.

So can I actually solve certain functional equations like this? And if true, how would the correct notation of the above be?

-

One way to think about this is that you are assuming that $f(x) = cx$ and then solving for the value of $c$.

But there is something much more interesting going on; you have started doing some abstract algebra without knowing it. $f$ is not a real number, but it does live in something called an algebra over a field, which is a special type of ring. In particular, $f$ lives in the algebra of continuous functions $\mathbb{R} \to \mathbb{R}$. In this algebra there is a multiplicative identity $f(x) = x$ which plays the role of the zeroth power, an addition, a multiplication, and a scalar multiplication by real numbers.

Many manipulations which are possible with ordinary real numbers are possible in rings and algebras; in particular, the first half of the proof of the quadratic formula carries through totally abstractly (the part where you complete the square).

Unfortunately, the second half does not. In other words, it is not true that there are only two solutions to the equation $f^2 = a$ in a general algebra. This is because algebras are not in general integral domains. There may be none or infinitely many!

However, in this special case $a$ is a positive real multiple of the identity, so we know it has at least two square roots (even though there may be more). These are the solutions that you found, and this method for finding them is perfectly valid.

This is a very important technique. It is often used in the case where $f$ is a differential operator as a concise way to solve linear homogeneous ODEs.

-
+1 Thank you very much. That was the kind of answer I was looking for –  Dario Sep 12 '10 at 17:23

In fact this belongs to a functional equation of the form http://eqworld.ipmnet.ru/en/solutions/fe/fe1220.pdf.

Let $\begin{cases}x=u(t)\\f=u(t+1)\end{cases}$ ,

Then $u(t+2)=u(t+1)+u(t)$

$u(t+2)-u(t+1)-u(t)=0$

$u(t)=C_1(t)\left(\dfrac{1+\sqrt{5}}{2}\right)^t+C_2(t)\left(\dfrac{1-\sqrt{5}}{2}\right)^t$ , where $C_1(t)$ and $C_2(t)$ are arbitrary periodic functions with unit period

$\therefore\begin{cases}x=C_1(t)\left(\dfrac{1+\sqrt{5}}{2}\right)^t+C_2(t)\left(\dfrac{1-\sqrt{5}}{2}\right)^t\\f=C_1(t)\left(\dfrac{1+\sqrt{5}}{2}\right)^{t+1}+C_2(t)\left(\dfrac{1-\sqrt{5}}{2}\right)^{t+1}\end{cases}$ , where $C_1(t)$ and $C_2(t)$ are arbitrary periodic functions with unit period

-

Whether or not $f$ is linear, the equation can in fact be rewritten as $F^2 = F + 1$, in a suitable interpretation where to a function $f$ is associated a linear operator $F$.

Let $V$ be the vector space of sums $aX + bf(X)$. Denote by $F$ the operator that takes an element of $V$ to its composition with $f$, that is, $F (h(x)) = h(f(x))$. Let $1$ denote the identity operator on $V$.

Then $F$ is linear (from the definition), and satisfies $F^2=F+1$ as one can check on basis elements.

I have been temporarily but deliberately unclear as to whether $V$ is the 2-dimensional space of formal sums with basis vectors $x$ and $f(x)$, or the at most 2-dimensional space of functions of that form. The question of whether $f$ is linear is the same as asking whether the second space is one-dimensional, which is no longer an algebraic question but one of analysis using regularity assumptions on $f$. (In particular, seeing $f$ as an operator or 2x2 matrix $F$, illuminates but does not quite trivialize the problem of showing that linear functions are the only continuous solutions to the functional equation. Additional arguments are needed.) The equation $F^2 = F + 1$ holds in both interpretations.

-

Assume $f$ is a linear transformation, then linear algebra lets us give it a matrix representation $f(x) = F \cdot x$. It is also the case that $f \circ g = F G$, function composition is represented by matrix multiplication.

In your derivation you do not make any distinction between $f$ and $F$, this is fine as long as you know you are doing it. Also the matrix $F$ is a 1x1 because $\mathbb{R}$ is a 1-dimensional vector space.

That is why we have:

$$\begin{eqnarray} f(f(x)) &= f(x) + x \\ \iff \\ F^2 &= F + I \\ \iff \\ \varphi^2 &= \varphi + 1 \end{eqnarray}$$

(Where $f(x) = F \cdot x = \varphi x$)

The only problem is that we cannot be sure $f$ is a linear transform just based on what was told. So it is not known whether this gives all solutions.

-
+1 Thank you very much –  Dario Sep 12 '10 at 17:25