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.

$\endgroup$
  • $\begingroup$ This reminds me of the asymptotic expression for the partition function. If there's anything to that, then it may be that one needs to use the circle method from analytic number theory to get your asymptotic. $\endgroup$ – Gerry Myerson Apr 1 '12 at 0:36
  • $\begingroup$ $e^{1/(1-z)}=ee^{z/(1-z)}$ so (as I'm sure you know) your $u_n$ differ from the OEIS entries only by a factor of $e$ and that $n$-factorial. It's true that the OEIS page gives no reference to a proof, but it does give references to a number of discussions of the sequence - have you followed up on them? The reference to the Flajolet book strikes me as promising (though I don't have the book handy). I note OEIS references to partitions, which strengthens my conviction that the Hardy-Littlewood circle method is applicable. $\endgroup$ – Gerry Myerson Apr 1 '12 at 6:48
  • $\begingroup$ @GerryMyerson The Flajolet reference only helps in that it suggests that the function $e^{z/(1-z)}$ might submit to the saddle-point method. This has been difficult for me to apply. $\endgroup$ – awwalker Apr 1 '12 at 22:20
  • $\begingroup$ Me, too. So it appears that answering, "How would one derive asymptotic results such as these" with "Use the saddle-point method" would not satisfy you. Perhaps it's time to find a good exposition of the method, try to apply it to the problem at hand, and come back to m.se with a more specific question when/if you get stuck. $\endgroup$ – Gerry Myerson Apr 2 '12 at 2:03
  • 1
    $\begingroup$ 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). $\endgroup$ – Gerry Myerson Apr 2 '12 at 5:08
5
$\begingroup$

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$.

$\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.