Solving a functional equation symbolically

How would i go about manipulating the following:

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

To find f(x) symbolically?

For instance, how would i go about finding f(0) given that equation?

• f[x_]:=a x with a the solution of a^3 == a^2 + 1 gives three solutions. There may well be others. – bbgodfrey Nov 30 '16 at 23:17
• Do you want to know how to program the software Mathematica to solve this problem, which is what this site is about? – Michael E2 Nov 30 '16 at 23:18
• @MichaelE2 Yes, i would like to know how to program mathematica to solve this composite equation. – J.S.K Nov 30 '16 at 23:32
• OK. It was unclear, because the problem is not posed with proper Mathematica syntax. – Michael E2 Nov 30 '16 at 23:55

We re-cast the equation as a recurrence relation. Taking \begin{align*} x_n&=x,\\ x_{n+1}&=f(x_n),\\ x_{n+2}&=f(f(x_n)),\\ x_{n+3}&=f(f(f(x_n))), \end{align*} this becomes the relation $$x_{n+3}=x_{n+2}+x_n.$$

We now use Mathematica's RSolve:

RSolve[x[n + 3] == x[n + 2] + x[n], x[n], n]
(* {{x[n] ->
C Root[-1 - #1^2 + #1^3 &, 1]^n +
C Root[-1 - #1^2 + #1^3 &, 2]^n +
C Root[-1 - #1^2 + #1^3 &, 3]^n}} *)

Evidently, there are three linearly independent solutions. These functions are just multiplication by the roots of the polynomial -1 - x^2 + x^3, e.g.

f[x_, n_ /; 1 <= n <= 3] := x Root[-1 - #1^2 + #1^3 &, n]

This shows that bbgodfrey's guess of a solution in their comment was all of the solutions.