# Recurrence relation: composition of a polynomial function

Let $f(x)=a+bx^2$. Define $f_n(x)$ to be the $n$-fold composition of $f$. That is $$f_1(x)=f(x)$$ $$f_2(x)=f \circ f(x)$$ $$f_n(x)=f \circ f_{n-1}(x), n \ge 2$$

Is there a way to find a formula for $f_n$?

I tried to write down $f_2$, $f_3,\ldots$, but I don't see any pattern.

-

## 2 Answers

After a simple change of variables, you will be iterating $z^2+c$ for some $c$. There is a simple formula for the $n$th iterate when $c=0$ or $c=-2$. But not otherwise.

added

Double-angle formula: $\cos 2\theta = 2\cos^2-1$, so if we write $z=2\cos\theta$, then we get $f_1 = z^2-2 = 2\cos 2\theta$ ; $f_2 = (z^2-2)^2-2 = 2\cos 4\theta$ ; and so on ... $f_n = 2\cos(2^n\theta)$. If you like, put $\theta = \arccos(z/2)$ into these.

-
I can't figure the simple expression for the case $c=-2$. I tried $$f_1=z^2-2$$ $$f_2=z^4-4z+2$$ $$f_3=f_2^2-2$$ But at $f_3$, I'm blocked, and I can't identify a formula. Thanks. – Nicolas Essis-Breton Sep 22 '11 at 14:25
For the $c=-2$ case, remember the double-angle formula for cosines. – GEdgar Sep 22 '11 at 14:48
Thanks GEdgard. Thanks everybody for your input. – Nicolas Essis-Breton Sep 22 '11 at 18:28
Sorry, I thought I had it clear, but I'm not sure of how to apply the double-angle formula here. Can you show me for $f_2$. Thanks. – Nicolas Essis-Breton Sep 22 '11 at 21:35
Thank you very much GEdgar. It's was the first for me to use the angle formula is such context. I was very hesitant at each step. But your precision make me confident now. Thanks. – Nicolas Essis-Breton Sep 23 '11 at 10:42

I don't believe there is a "nice" formula for $f_n$ or even a pattern. Here's my reasoning:

If the graph of $y = a + bx^2$ intersects the line $y=x$, then there can be chaotic behavior in the values $f_n(x)$ for general $x$. See the neat animation on the Wiki article for "cobweb plot":

http://en.wikipedia.org/wiki/Cobweb_plot

Hope this helps!

-
Of course, there are some special cases of note. If $a = 0$, then it's fairly easy to find the general formula: $f_n(x) = b^{2^n - 1}x^{2^n}$. – Shaun Ault Sep 22 '11 at 1:16