# Asymptotics of coefficients of implicitely defined generating function

I have two integer sequences $\{a_n\}_{n=0}^\infty$ and $\{b_n\}_{n=0}^\infty$. Explicit formulas for the $a_n$ are known and their asymptotic growth is fully understood. My wish is to also understand the asymptotics of the numbers $b_n$.

The corresponding power series $A(x) = \sum_{n=0}^{\infty} a_n x^n$ and $B(x) = \sum_{n=0}^{\infty} b_n x^n$ are related by an equation of the form

$$A(x) = B(p(x,A(x)))$$

where $p$ is a simple bivariate polynomial ($p(x,y) = xy^3$ in my concrete case).

I was able to find at least the exponential rate of growth of the $b_n$ with my own pedestrian methods (essentially by determining the radius of convergence of $B(x)$). However, I was not able to determine the subexponential factor.

I have been looking for a general method in the "Analytic Combinatorics" book of Sedgewick and Flajolet, but did not find anything that seems to match my problem. I would appreciate any hints or pointers to solutions of similar problems.

• It highly depends on concrete example. General strategy could be described as "first, study asymptotics of $B$ as function, then use contour integral representations of coefficients and apply some tools for asymptotics of integrals" Jun 18, 2015 at 19:54
• It seems to me that your functional equation is equivalent to $B^{-1}(x) = p(A^{-1}(x),x) = x^3 A^{-1}(x)$, obtained by starting with the $x \to A^{-1}(x)$ substitution. So, the coefficients of $B^{-1}(x)$ and $A^{-1}(x)$ are very simply related. If you have a way of estimating the asymptotics of a generating function from its inverse, then you'd be done. Jun 18, 2015 at 21:35
• Hmm, by inspection, if $B^{-1}(x)$ has a Taylor series expansion about $0$, then $B(x)$ would have a non-trivial Puiseux expansion about $0$, which fit your hypthesis about it. Perhaps in the end this means that this idea might not be applicable in your situation. Jun 18, 2015 at 21:40
• Put $z=x\cdot A^3(x)$, i.e. $x={z \over A^3(x)}$. By Lagrange Inversion $b_0=a_0=1$ and $b_n=[z^n] A(x)=[t^n] {-1 \over 3n-1}{1\over A^{3n-1}(t)}$ for $n\geq 1$. Now use Thm VIII.8 in Analytic Combinatorics''.
Since $a_0\neq 0$ there is (by the (formal) Lagrange theorem) a unique formal power series $x=x(z)$ solving $x={z \over A^3(x)}$, and $A(x(z))=B(z)$ because $A(x)=B(x\,A^3(x))$. Expanding $A(x)$ using the Lagrange inversion formula gives $a_0=b_0$ and $$b_n=[z^n]A(x)={1 \over n}[t^{n-1}] A^\prime(t){1 \over A^{3n}(t)}=[t^n]{-1 \over 3n-1} {1 \over A^{3n-1}(t)}$$ for $n\geq 1$ (the latter equation because $[t^{n-1}]f^\prime(t)=n[t^n] f(t)$).
In Composita and its properties section 6, Theorem 28 there is an analysis of coefficients of generating functions fulfilling the functional equation: $$A(x)=B(xA(x)^m)$$ which could be helpful.