3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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.) $\endgroup$ – Semiclassical May 3 '17 at 11:30
  • $\begingroup$ 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... $\endgroup$ – Jon Noel May 5 '17 at 21:23
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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