A while ago I asked a question on trigonometric functions that are iteratively periodic. That is, after a finite number of iterations (compositions of the function with itself) the function returns to its original form. In other words, for some $k \in \mathbb{Z}_{>1}$ we have $f^{[k]} (x) = f^{[1]}(x) =: f(x)$.
In the question, I also mentioned some counterexamples that are not iteratively periodic. In these instances, I found functions that yield Fibonacci numbers upon iteration:
- Consider $m(x) := m^{[1]}(x) = \cot(\arcsin(x)) = \frac{\sqrt{1-x^{2}}}{x}$. Then, $m^{[n]}(x) = \sqrt{ \frac{F_{n} - F_{n+1}x^{2}}{F_{n}x^{2} - F_{n-1}} \cdot (-1)^{n+1} } $ for $n >1$, where $F_{n}$ is the $n$'th Fibonacci number.
- Define $l(x) := l^{[1]}(x) = \cos(\arctan(x)) = \frac{1}{\sqrt{1+x^{2}}} $. In this case, $l^{[n]} (x) = \sqrt{\frac{F_{n} + F_{n-1}x^{2}}{F_{n+1} + F_{n}x^{2}}}$ for $n>1$.
Question: though $m(\cdot)$ and $l(\cdot)$ are not the most complex functions, I wonder whether there exist functions that are even simpler than these and generate fibonacci numbers as well upon iteration. On could consider a rigorous definition of function complexity, but if that's not your thing then a simple function from a more intuitive sense (as little operations and inputs as possible) suffices as well. The function does not have to be trigonometric.
Take $f(x) = 1+\frac{1}{x}$. Then $$f^{[n]}(x) = \frac{F_{n+1} x +F_n}{F_n x + F_{n-1}}$$
A related one is $g(x) = \frac{1}{1+x}$. Then $$g^{[n]}(x)=\frac{F_{n-1}x+F_n}{F_n x+F_{n+1}}$$
I doubt there are "simpler" functions that those two whose iterations involve Fibonacci numbers.
This functions also have other amusing properties, for example:
If you define $f^{[n]}(x)$ for $n<0$ as the iterations of the inverse function, and extend in the usual way the Fibonacci numbers to negative indices, the formula above remains valid.
We have $\displaystyle \lim_{n\to\infty} f^{[n]}(1) = \lim_{n\to\infty}\frac{F_{n+2}}{F_{n+1}}=\phi$, the golden ratio.