# $\sum \limits_{n \geq 0}a_n \frac{x^n}{n!}=e^{x+x^2/2}$ implies $a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$

Prove the following asymptotic formula for the exponential generating function coefficients of $e^{x+x^2/2}$: $\; \; a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$

Stanley Richard writes in equation 1.12 of his book Enumerative Combinatorics the preceding formula without a proof, claiming it is 'routine with complex variable theory'.

It was already deduced that $a_n=\sum\limits_{j \geq 0} \binom{n}{2j}\frac{(2j)!}{2^jj!}$, so I tried to use Stirling's approximation on it and ended with a horrendous sum involving $(n-2j)^{n-2j}$, which seems clearly off-the-path.

• This is on the internet, it is at the end of chapter 8 "Saddle point asymptotics" of Analytic Combinatorics by Flajolet and Sedgewick. They work this one as their example. – Marko Riedel May 8 '15 at 20:18

Note: This answer follows section 5.4, example 2 of H.Wilf's Generatingfunctionology

Observe that $f(x)=e^{x+\frac{x^2}{2}}$ is an entire function which can therefore be written as power series \begin{align*} f(x)=\sum_{n\geq 0}a_nx^n \end{align*} converging everywhere in the complex plane. For this type of function we can check if Hayman's method is applicable.



Theorem (Hayman): Let $f(x)=\sum_{n\geq 0}a_nx^n$ be an admissible function. Let $r_n$ be the positive real root of the equation $a(r_n) = n$, for each $n = 1,2,\ldots$ where $a(r)$ is given by \begin{align*} a(r)=r\frac{f^{\prime}(r)}{f(r)}. \end{align*} Then \begin{align*} a_n\sim \frac{f(r_n)}{r_n^n\sqrt{2\pi b(r_n)}}\qquad\qquad (n\rightarrow \infty)\tag{1} \end{align*} where $b(r)$ is given by \begin{align*} b(r)=ra^{\prime}(r)=r\frac{f^{\prime}(r)}{f(r)}+r^2\frac{f^{\prime\prime}(r)}{f(r)}-r^2\left(\frac{f^{\prime}(r)}{f(r)}\right)^2. \end{align*}

We have to check if our function $f(x)$ is admissable in order to apply Hayman's method. One criterion for admissability is according to H.Wilf, section 5.4 (E):

Let $P(x)$ be a nonconstant polynomial with real coeffcients, and let $f(x) = e^{P(x)}$. If $a_n > 0$ for all suffciently large $n$, then $f(x)$ is admissible in the plane.

Indeed, since $f(x)=e^{x+\frac{x^2}{2}}$ has this shape with $P(x)=x+\frac{x^2}{2}$ and the coefficients $a_n=\sum\limits_{j \geq 0} \binom{n}{2j}\frac{(2j)!}{2^jj!}>0$ for all $n$, we can apply this method.

Calculation of $a(r)$ and $b(r)$

We find that

Calculation of $r_n$

According to Hayman's theorem we have to solve the quadratic equation \begin{align*} a(r)=r+r^2=n\tag{2} \end{align*} and get \begin{align*} r=-\frac{1}{2}\pm\frac{1}{2}\sqrt{4n+1} \end{align*} Since we need the positive real root $r_n$, we obtain using the binomial series representation of the square root of $n$ following asymptotic estimation for $r_n$ \begin{align*} r_n&=-\frac{1}{2}+\sqrt{n+\frac{1}{4}}\\ &=-\frac{1}{2}+\sqrt{n}\left(1+\frac{1}{4n}\right)^{\frac{1}{2}}\\ &=-\frac{1}{2}+\sqrt{n}\sum_{k\geq 0}\binom{\frac{1}{2}}{k}\frac{1}{(4n)^{k}}\\ &=-\frac{1}{2}+\sqrt{n}\left(1+\frac{1}{8n}+\mathcal{O}(n^{-2})\right)\tag{3}\\ &=\sqrt{n}-\frac{1}{2}+\frac{1}{8\sqrt{n}}+\mathcal{O}(n^{-\frac{3}{2}})\tag{4} \end{align*}

Comment:

• In (3) we take the summands with $k=0,1$, since every other summand with $k>1$ has already order of $\mathcal{O}(n^{-2})$

To calculate the asymptotic estimation for $a_n$ we need the asymptotic estimations for $r_n^n, f(r_n), b(r_n)$. We start with

Asymptotic estimation of $f(r_n)$

Comment:

• In (5) we use the relationship $r_n+r_n^2=n$ from (2)

• In (6) we use the expansion of $r_n$ in (4) up to the order of $n^{-\frac{1}{2}}$

Asymptotic estimation of $b(r_n)$

Comment:

• In (7) we use the relationship $r_n+r_n^2=n$ from (2)

• In (8) we use the expansion of $r_n$ in (4) up to the order of constants

Asymptotic estimation of $r_n^n$

We use $a^b=\exp(b\ln(a))$ and the Taylor series for $\ln$ to get \begin{align*} r_n^n&=\left(\sqrt{n}-\frac{1}{2}+\mathcal{O}(n^{-\frac{1}{2}})\right)^n\\ &=n^{\frac{n}{2}}\left(1-\frac{1}{2\sqrt{n}}+\mathcal{O}(n^{-1})\right)^n\\ &=n^{\frac{n}{2}}\exp\left(n\ln\left(1-\frac{1}{2\sqrt{n}}+\mathcal{O}(n^{-1})\right)\right)\\ &=n^{\frac{n}{2}}\exp\left(-n\sum_{k\geq 1}\left(\frac{1}{2\sqrt{n}}+\mathcal{O}(n^{-1})\right)^k\frac{1}{k}\right)\tag{9}\\ &=n^{\frac{n}{2}}\exp\left(-n\left(\frac{1}{2\sqrt{n}}+\mathcal{O}(n^{-1})\right)\right)\tag{10}\\ &=n^{\frac{n}{2}}\exp\left(-\frac{1}{2}\sqrt{n}+\mathcal{O}(1)\right)\\ &\sim n^{\frac{n}{2}}e^{-\frac{\sqrt{n}}{2}}\qquad\qquad\qquad\qquad\qquad\qquad (n\rightarrow \infty) \end{align*}

Comment:

• In (9) we use $\mathcal{O}(n^{-1})=-\mathcal{O}(n^{-1})$

• In (10) we take the first summand with $k=1$, since every other summand with $k>1$ has already order of $\mathcal{O}(n^{-1})$

Final step: Asymptotic estimation of $a_n$

We can now put everything together to calculate the asymptotic expansion of $a_n$ according to (1). One final aspect we have to consider is, that the admissability of $e^{x+\frac{1}{2}x^2}$ was based upon the representation $$e^{P(x)}=\sum_{n\geq 0}\frac{t_n}{n!}$$

So, we have the situation

\begin{align*} a_n=\frac{t_n}{n!}\sim \frac{f(r_n)}{r_n^n\sqrt{2\pi b(r_n)}}\qquad\qquad (n\rightarrow \infty) \end{align*} and we will therefore also take the Stirling approximation of $n!$

$$n!\sim \sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n}\qquad\qquad\qquad\qquad (n\rightarrow \infty)$$

We finally obtain

\begin{align*} a_n &\sim n!\frac{f(r_n)}{r_n^n\sqrt{2\pi b(r_n)}}\\ &=\sqrt{2\pi}n^{n+\frac{1}{2}}e^{-n} \frac{e^{\frac{n}{2}+\frac{1}{2}\sqrt{n}-\frac{1}{4}}}{n^{\frac{n}{2}}e^{-\frac{\sqrt{n}}{2}}\sqrt{4\pi n}}\\ &=\frac{1}{\sqrt{2}}n^{\frac{n}{2}}e^{-\frac{n}{2}+\sqrt{n}-\frac{1}{4}} \end{align*}

• Thanks. I couldn't spot an actual proof of Hayman's Method in the linked text of Wilf, oddly enough... Is it present anywhere in there? – Emolga May 9 '15 at 22:21
• @Leullame: You're welcome! A proof isn't in there. You could find a proof e.g. in Flajolets and Sedgewicks Analytic Combinatorics (Theorem VIII.4). You could also consult the original paper from Hayman from 1965. There are free available versions online as far as I remember. Best regards, – Markus Scheuer May 9 '15 at 22:49