# What are solutions of that functional equation?

How to find all the functions $f:[0,\infty)\rightarrow [0,\infty)$ satisfying the functional equation $$f(f(x))=-4f(x)+3x?$$ I deduced $f(x) \le \frac 3 4 x.$

Fix some $x$, and consider the sequence given by $$T_0 = x$$ and $$T_{k+1} = f(T_k)$$ for all $k \geq 0$.

The functional equation then tells us that the sequence $(T_n)$ satisfies the recurrence relation $$T_{k+2}+4T_{k+1}-3T_k=0$$

The roots of the characteristic equation $\lambda^2+4\lambda-3$ are $\phi_1=-2+\sqrt{7}$ and $\phi_2=-2-\sqrt{7}$. All possible solutions to the recurrence are given by

$$T_n=A(x)\phi_1^n + B(x)\phi_2^n$$

where $A$ and $B$ are some values which depend only on $x$ and not on $n$.

Now since the codomain of $f$ is the non-negative reals, we must have that $T_n\geq 0$ for all $n$, and so

$$A\phi_1^n + B\phi_2^n\geq 0$$ for all $n$, or equivalently

$$A + B\phi^n \geq 0$$ for all $n$, where $$\phi=\frac{\phi_2}{\phi_1}$$

We note that $\phi<0$ and that $|\phi|>1$, and so $|\phi|^n\to\infty$ as $n\to\infty$. In particular, $\phi^n$ takes arbitrarily large (in magnitude) positive and negative values.

Now if $B<0$ then we see that for large enough even $n$, we would have that $T_n<0$. Similarly, if $B>0$ then for large enough odd values of $n$ we would also have that $T_n<0$. Thus to have $T_n\geq 0$ for all $n$, we must have that $B=0$.

The solution to the recurrence then becomes $$T_n=A\phi_1^n$$ for all $n$. Taking $n=0$ we see that $A=x$. Thus $$T_n = x(-2+\sqrt{7})^n$$ for all $n$.

In particular, $$f(x)=T_1=x(-2+\sqrt{7})$$

for all $x$, which we can check satisfies the functional equation.

Edit: Another approach

Another approach continues from your observation that $$0x \leq f(x) \leq \frac{3}{4} x$$ for all $x$.

Suppose that $\lambda x \leq f(x)$ for all $x$. Then the functional equation gives us $$-4f(x)+3x=f(f(x))\geq \lambda f(x) \geq \lambda^2 x$$ for all $x$, and so $$f(x) \leq \frac{3-\lambda^2}{4} x$$ for all $x$.

Similarly, if $f(x) \leq \lambda x$ for all $x$, then we get that $$-4f(x)+3x \leq \lambda^2 x$$ for all $x$, and so $$f(x) \geq \frac{3-\lambda^2}{4} x$$ for all $x$.

(The above implicitly assumes that $\lambda \geq 0$, which will be the case in what we consider)

We see that if we define the sequence $(T_n)$ by $T_0=0$ and $$T_{n+1}=\frac{3-T_n^2}{4}$$ then $$T_{2k} x \leq f(x) \leq T_{2k+1} x$$ for all $x$.

We will now show that the sequence $(T_n)$ has a limit and that it is equal to $-2+\sqrt{7}$, which then solves the question.

The sequence is clearly bounded above by $\frac{3}{4}$. Also, since $\frac{3}{4} < \sqrt{3}$, the recurrence also shows that the sequence terms are all non-negative. (And hence are bounded below by $0$)

We now consider the odd and even indexed terms separately. Using the recurrence twice gives us that $$T_{n+2}=\frac{39+6T_n^2-T_n^4}{64}$$

Consider the function $g(x)=\frac{39+6x^2-x^4}{64}$. (So that $T_{n+2}=g(T_n)$) We note that $64g^\prime(x)=12x-4x^3$, and so for non-negative values of $x$, $g(x)$ is increasing provided that $x \leq \sqrt{3}$. In particular, we see that if $x \leq -2+\sqrt{7}$ then $g(x) \leq g(-2+\sqrt{7}) = -2+\sqrt{7}$, and similarly, if $-2+\sqrt{7} \leq x \leq \sqrt{3}$ then $-2+\sqrt{7}\leq g(x)$.

We see that if $T_n \leq -2+\sqrt{7}$ then $T_{n+2} \leq -2+\sqrt{7}$, and that if $T_n \geq -2+\sqrt{7}$ then $T_{n+2} \geq -2+\sqrt{7}$. In particular, since $T_0=0\leq -2+\sqrt{7}$, and $T_1=\frac{3}{4} \geq -2+\sqrt{7}$, we have that $$T_{2k}\leq -2+\sqrt{7}$$ and $$T_{2k+1} \geq -2+\sqrt{7}$$ for all $k$.

Now consider $g(x)-x$. We have that $$64(g(x)-x)=39-64x+6x^2-x^4=(x^2+4x-3)(x^2-4x+13)$$ which has the same sign as $(x^2+4x-3)$. The roots of $x^2+4x-3$ are $-2+\sqrt{7}$ and $-2-\sqrt{7}$, and so for non-negative values of $x$ we see that $g(x) \geq x$ if and only if $x \geq -2+\sqrt{7}$.

Combining all of our observations above, we see that the even indexed terms form an increasing sequence of real numbers which is bounded above, and that the odd indexed terms form a decreasing sequence of real numbers which is bounded below. Thus both of the sequences $(T_{2k})$ and $(T_{2k+1})$ have a limit. If $\lambda$ is either of these limits, then we have that $g(\lambda) = \lambda$ by passing to the limit in the recurrence for these sequences, and so $$(\lambda^2+4\lambda-3)(\lambda^2-4\lambda+13)=0$$ We know that $\lambda$ should be a non-negative real number, and so we get that $\lambda=-2+\sqrt{7}$. So the limit of both sequences is $-2+\sqrt{7}$.

This shows that $T_n\to -2+\sqrt{7}$ as $n \to \infty$, which completes the proof.

• it was fantastic, may you introduce me a book that help me know more about such equations? – R.N Sep 3 '15 at 10:00
• @RaziehNoori The general topic at work here is linear recurrence relations. Rather than a book, I would start by reading some notes online on the topic (or learning some basic linear algebra, if you haven't already). – Eric Auld Sep 3 '15 at 10:08
• Another approach (that I could write up as a separate answer, but I'm not sure if I should or if such a thing is usually done on this site) is to use the observations that $0x \leq f(x)\leq\frac{3}{4}x$ for all $x$ and then construct sequences of values $a_n$ and $b_n$ such that $a_n x \leq f(x) \leq b_n x$ for all $x$. You can find $a_n$ and $b_n$ such that the limit of each sequence is $-2+\sqrt{7}$ which then proves the same result as my answer above. – Dylan Sep 3 '15 at 22:13
• @Dylan You may very well add this new approach to the answer above. +1 already. – Did Sep 4 '15 at 6:31