13
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ 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" $\endgroup$
    – Fedor Petrov
    Jun 18, 2015 at 19:54
  • 1
    $\begingroup$ 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. $\endgroup$
    – Igor Khavkine
    Jun 18, 2015 at 21:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – Igor Khavkine
    Jun 18, 2015 at 21:40
  • 2
    $\begingroup$ See also Chapter 5 in Generatingfunctionology by Wilf, math.upenn.edu/~wilf/gfologyLinked2.pdf $\endgroup$
    – Per Alexandersson
    Jun 23, 2015 at 18:00
  • 1
    $\begingroup$ 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''. $\endgroup$
    – esg
    Jul 20, 2015 at 18:03

2 Answers 2

Reset to default
1
$\begingroup$

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)$).
The rhs is in many cases amenable to saddle point analysis, see e.g. section VIII.8 and Thm.VIII.8 in ''Analytic Combinatorics".

Improve this answer
$\endgroup$
0
7
$\begingroup$

There are some papers by V. Kruchinin addressing the composition of generating functions

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.