6
$\begingroup$

Let $\sum u_n z^n$ denote the power series of $e^{1/(1-z)}$. As our radius of convergence is $1$, it follows that $u_n$ exhibits sub-exponential growth. On the other hand, $\{u_n\}$ must grow supra-polynomially, else transfer theorems like those found in Singularity Analysis of Generating Functions would then imply that the singularity at $z=1$ is regular. Heuristically, it would appear that $u_n \sim \alpha n^{-3/4} e^{2\sqrt{n}},$ for some $\alpha \approx .162982$. This opinion is echoed, without support, as a comment on the OEIS page for A000262. Note: The sequence considered therein is the generating function of $e^{z/(1-z)}$, which has $\mathbb{Z}$ coefficients after scaling $u_n$ by $n!$

How would one derive asymptotic results such as these?

(Edited for spelling.)

Note: I've posted my own solution in the answers below. In short, the saddle-point method applies.

  • 1
    Nice. Probably best if you post as an answer, rather than as an edit to the question, and then accept it (if no one raises any mathematical objection).2012-04-02

1 Answers 1

5

I've managed to answer my own question, but I'll post it here.

As discussed in the comments above, the method of saddle point approximation works here. In short, $f(z):=e^{1/(1-z)}$ meets the sufficient conditions given in Graham et al's Handbook of Combinatorics, II (pg. 1175). It follows that $[z^n]f(z) \sim (2 \pi b(r_0))^{-1/2} f(r_0) r_0^{-n},$ where $r_0$ is the saddle point (where $f(z)z^{-n}$ is minimized as a function of $z$) and the function $b(z)$ is given by b(z) :=z \left( z \frac{f'(z)}{f(z)}\right)' = \frac{-z(1+z)}{(z-1)^3}, the latter only in this instance. Here, our saddle point is $r_0=\frac{1+2n-\sqrt{1+4n}}{2n},$ so - putting this all together - we conclude $ [z^n]f(z) \sim \frac{2^{n-\frac{3}{2}} e^{\frac{2 n}{\sqrt{4 n+1}-1}} \left(\frac{2 n-\sqrt{4 n+1}+1}{n}\right)^{-n}}{\sqrt{\pi } \sqrt{\frac{n \left(4 n^2-3 \sqrt{4 n+1} n+5 n-\sqrt{4 n+1}+1\right)}{\left(\sqrt{4 n+1}-1\right)^3}}} \sim \frac{e^{\sqrt{n}} \left(1-\frac{1}{\sqrt{n}}\right)^{-n}}{2 \sqrt{\pi } \sqrt{n^{3/2}}} \sim \frac{\sqrt{e}}{2\sqrt{\pi}} e^{2 \sqrt{n}} n^{-3/4}.$ Here, the omitted steps between steps (1) and (2) are easy to do by hand. As for this final step, it suffices to show $\lim_{n \to \infty} \left(1-\frac{1}{\sqrt{n}}\right)^{-n} e^{-\sqrt{n}}= \sqrt{e},$ which I'll leave as an interesting exercise. To finish up, we just note that $f(z) = e u(z)$, which gives us asymptotics for $\{u_n\}$. Note: the initial estimate $\alpha \approx .162982$ is quite bad. The actual value is $\approx 0.171099$.