# Functional recursion equations

Lets denote n-times recursion as: $$f(f(f ... f(x) ...)) = ({^nf}(x)), ({^0}f(x))=x$$ My question is: is there general approach to solve 'algebraic' functional equation? $$a_n({^nf}(x))+a_{n-1}({^{n-1}f}(x)) ... + a_0x = 0$$ For example: ${^3f}(x) - x = 0$ has 2 known to me solutions: $f(x) = \frac{1}{1-x}$, $f(x)=x$ and ${^2f}(x) - x = 0$ has 2 simple solutions: $f(x) = 1-x$, $f(x)=x$

In some special cases solutions are easy to find, in another - not. I will be thankful for any references to research done in this area.

For example, $({^2}f)(x)=x$ valid for all functions $y=f(x)$ that can be expressed in the form $\psi(x,y)=\psi(y,x)$, i.e. has parameters symmetry.

• You know that just for $n>4$ and even $f(x)=x$ there is not a "general approach"... So your general problem is hopeless. – guestDiego Sep 30 '16 at 18:16
• Oh... well. That is why I am here .. to ask. Reading your comment, even a case ${^n}f(x) = x$ is hopeless. – hOff Sep 30 '16 at 18:44
• @guestDiego The case $f(x) = x$ is pretty trivial, whatever $n$, since then ${}^n f(x) = x$ for all $n$. It's pretty hopeless for $f(x) = x^k$ with $k > 1$, since then ${}^n f(x) = x^{k^n}$. – Daniel Fischer Sep 30 '16 at 18:48
• How do I solve for a function when I can't even solve for a root in a 5th degree polynomial? $\ddot\frown$ – Simply Beautiful Art Sep 30 '16 at 20:46
• @Daniel Fischer You are completely right. Just a lapsus originated by the wrong assumption ${}^n f(x) = x^n$. However you found a way out. Thank you – guestDiego Oct 1 '16 at 15:07

For some class of function there is the concept of Carleman/Bell matrices, converting the problem of functional iteration into that of matrix-powers.
Basically that concerns functions for which you have a power-series having a nonzero radius of convergence.
The best adapted cases are such functions, where the power series has no constant term: then the Carleman-matrix is triangular and admits powers and often even fractional powers giving power series for iterations and even fractional iterations accordingly.

The field is very wide, has a lot of, sometimes complicated, requirements. Just to make the above a bit more intuitive:

Consider a matrix $F$ containing columnwise the coefficients of the formal powerseries of some function $f(x)$ and of its powers $f(x)^0, f(x)^1, f(x)^2, ...$
Consider then a vectorexpression $V(x) = [1,x,x^2,x^3,...]$
Then the idea for the Carleman-matrix is, to be able to evaluate
$$\begin{array} {rll} V(x) \cdot M &= [1,f(x),f(x)^2, ...] & \text{ which is also }\\ V(x) \cdot M &= V(f(x)) & \text{ and then of course }\\ V(f(x)) \cdot M &= V(f°^2(x)) \\ V(f°^2(x)) \cdot M &= V(f°^3(x)) \\ \cdots & \text{ and finally }\\ V(x) \cdot M^h &= V(f°^h(x)) \end{array}$$ Then fractional iterates are constructed - at least their formal power series- if fractional powers of $M$ can be constructed, for instance by diagonalization or matrixlogarithm/matrixexponentiation.

If this is all possible with some given function $f(x)$ then ony can approach your examples of functional equations on iterations with polynomials with the powers of F or even series on F. For instance, one approach for solving the problem of tetration is to approximate the solution of $\small (I-F)^{-1}$ (which is like a geometric series with matrix $F$ as quotient, an example can be found for instance as a sidenote in an article of P. Walker on the fractional iterate of the $\exp()$. Such series are called "Neumann-series" and have of course their own strong requirements)

As I said above, this is far from being trivial and as well technical as principal problems must be solved, or often cannot be solved. Also this is only one approach to that problem of function-composition and -iteration, having already a vast amount of literature - books and online available articles...

Sidenote: the diagonalization (if possible) of a Carlemanmatrix F for some function $f(x) = a_1x + a_2x^2 + ...$ reflects/implements also the concept of the Schröder-function (That concept has been introduced around 1890 by Ernst Schröder, and developed later by G. Koenigs and others) . In the 1950/60/70 E. Jabotinsky developed specifically the attempt using the Carlemanmatrix.

• Thanks. At least it paves the way to solution for certain functional classes. – hOff Oct 23 '16 at 16:40