# Extracting Asymptotics of a Sequence from an Equation Involving a Generating Function

Let $f:\mathbb{R}\to \mathbb{R}$ be a sufficiently well behaved function and $g:\mathbb{N}\to \mathbb{N}$. Suppose that $a:\mathbb{N}\to \mathbb{R}$ is a sequence defined by the following equation:

$$\sum_{n=1}^{\infty} \frac{a(n)}{n!}x^nf(x)^{g(n)} = x.$$

Question: Is there any good way to get information about the asymptotics of $a(n)$? If not, is there any good way to simply determine a single value of the sequence, e.g., $a(100)$?

The specific example that I am looking at is $f(x)=e^{-x}$ and $g(n) = \frac{n(n+1)}{2}$, i.e.,

$$\sum_{n=1}^{\infty} \frac{a(n)}{n!}x^ne^{-x\frac{n(n+1)}{2}} = x.$$

The sequence $a(n)$ is entry A195737 in the Online Encyclopedia of Integer Sequences (OEIS) and the first 200 terms of it can be found there.

In my example, it seems to me that $a(n)$ should be roughly $\frac{n^nn!}{e^{o(n)}}$ but I would like a rigorous argument for this (and, if possible, better aymptotics).

By the way, for any function $f$ (perhaps with the condition that $f$ is injective on $(0,\varepsilon)$, or something like that) if we had $g(n)=n$, then $\sum_{n=1}^\infty \frac{a(n)}{n!}x^n$ would simply be the inverse of $xf(x)$ (this is easy to see), and this could help us get some information about $a(n)$. The main difficulty that I am having is that, in my example, $g(n)\neq n$.

Edit: In the answers below, I give a simple way of obtaining a recursive expression for $a(n)$, provided that $f(0)\neq 0$. However, this doesn't address the issue of the asymptotics of $a(n)$. I would be happy to get an answer to the following question:

Question: Can something like the saddle-point method/Cauchy's Integral Formula be applied here? Normally, it seems that this method is used to estimate the entries of a sequence $a(1),\dots, a(n)$ by integrating its generating function on a circle around the origin in the complex plane. The situation here seems somewhat different, but can the method be somehow adapted?

• The main source I know for asymptotics of coefficients of generating functions is Flajolet & Sedgewicks Analytic Combinatorics. No guarantee it has what you want, but it's a good place to start (especially since the author has a free PDF version on his site---see link.) – Semiclassical May 3 '17 at 11:30
• So, I have done some thinking and experimentation and it seems that if f(x) = e^(-x), then a(n) = Sum_{k=1,...,n-1} (-1)^(k-1)*binom(n,k)*g(n-k)^k*a(n-k). (This may depend on properties of the function g... I have only verified it for g=n and g=n(n+1)/2). I would be happy to accept any answer which can explain this... – Jon Noel May 5 '17 at 21:23

## 1 Answer

Okay, I have worked out how to get a recursive formula for $a(n)$, but this does not answer the question of asymptotics (which is probably too hard to do in general). Suppose that $f(0)\neq 0$. For each fixed $n$, write out the Maclaurin series for $f(x)^{g(n)}$: $$f(x)^{g(n)} = \sum_{k=0}^\infty \frac{b_n(k)}{k!}x^k$$ and note that $b_n(0)\neq0$ for all $n$ since $f(0)\neq0$. Now, substitute this in as follows $$x = \sum_{n=1}^\infty \frac{a(n)}{n!} x^n f(x)^{g(n)} = \sum_{n=1}^\infty \frac{a(n)}{n!} x^n\left(\sum_{k=0}^\infty \frac{b_n(k)}{k!}x^k\right).$$ We can now compute the coefficient of $x^n$. Since the coefficient of $x$ is one (as the expression is equal to $x$), we get $$a(1)\cdot b_1(0) = 1$$ and so $a(1)=\frac{1}{b_1(0)}$ since $b_1(0)\neq 0$. For $n\geq2$, the coefficient of $x^n$ is zero, and so $$\sum_{k=0}^{n-1}\frac{a(n-k)b_{n-k}(k)}{(n-k)!k!} = 0.$$ This allows us to write $$a(n) = -\sum_{k=1}^{n-1}\binom{n}{k}\frac{a(n-k)b_{n-k}(k)}{b_n(0)}$$ since $b_n(0)\neq 0$, and so we have a recursive expression for $a(n)$.

By the way, if $f(x)=e^{-x}$, then $b_n(k) = (-1)^kg(n)^k$ so we get $$a(n) = \sum_{k=1}^{n-1}(-1)^{k-1}\binom{n}{k}a(n-k)g(n-k)^k$$ which is kind of nice.