# What is the coefficient of $x^{2k}$ in the $n$-th iterate, $f^{(n)}(x)$, if $f(x)=1+x^2$?

Let $f(x)=1+x^2$, and its $n$-th compositional iterate $f^{(n)}=\sum_{k=0}^N c_{k,n} x^{2k}$, where $N=2^{n-1}$. What do we know about $c_{k,n}$?

• What do you mean by $n^{th}$ iterate?
– user17762
Commented Apr 18, 2013 at 17:43
• $f(f(f \cdots f(x)\cdots))$, that is $f$ composed with itself $n$ times. Commented Apr 21, 2013 at 15:28
• I presume you know Faà di Bruno already? Commented Apr 23, 2013 at 17:27

There is some computation for iteration of $M(x) = x^2+c$ in the last section of G. Edgar, "Fractional iteration of series and transseries", to apear in Trans. Amer. Math. Soc. LINK
Put $c=1$ in (19) to get $$M^{[s]} = x^{2^s}\left( 1+2^{-1+s}x^{-2}-2^{-1}x^{-2^{s+1}}+2^{-3+2s}x^{-4} +2^{-2+s}x^{-2-2^{s+1}} +O(x^{-6}+x^{-2^{s+2}})\right)$$ for the $s$th iterate. More terms could be done by the same method, just more computation. The motivation there is fractional $s$, but it holds in particular for integer $s$.
So we have these: \begin{align*} M^{[0]} &= x+O(x^{-3}) \\ M^{[1]} &= x^2+1+O(x^{-4}) \\ M^{[2]} &= x^4+2x^2+2+O(x^{-2}) \\ M^{[3]} &= x^8+4x^6+8x^4+O(x^2) \end{align*} When $s$ is a positive integer, of course there are no negative powers.