2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Marko Riedel May 8 '15 at 20:18
4
$\begingroup$

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.

We start with

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

We find that

\begin{align*} a(r)=r\frac{f^{\prime}(r)}{f(r)}=r+r^2\qquad\text{ and }\qquad b(r)=ra^{\prime}(r)=r+2r^2 \end{align*}

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

We obtain \begin{align*} f(r_n)&=e^{r_n+\frac{1}{2}r_n^2}\\ &=e^{\frac{1}{2}(r_n+n)}\tag{5}\\ &=e^{\frac{n}{2}}e^{\frac{r_n}{2}}\\ &=e^{\frac{n}{2}}\exp\left(\frac{1}{2}\sqrt{n}-\frac{1}{4}+\mathcal{O}(n^{-\frac{1}{2}})\right)\tag{6}\\ &=\exp\left(\frac{n}{2}+\frac{1}{2}\sqrt{n}-\frac{1}{4}+\mathcal{O}(n^{-\frac{1}{2}})\right)\\ &\sim e^{\frac{n}{2}+\frac{1}{2}\sqrt{n}-\frac{1}{4}}\qquad\qquad\qquad\qquad\qquad\qquad (n\rightarrow \infty) \end{align*}

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

We get \begin{align*} b(r_n)&=r_n+2r_n^2\\ &=n+r_n^2\tag{7}\\ &=n+\left(\sqrt{n}+\mathcal{O}(1)\right)^2\tag{8}\\ &\sim 2n\qquad\qquad\qquad\qquad\qquad\qquad (n\rightarrow \infty) \end{align*}

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*}

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Emolga May 9 '15 at 22:21
  • 1
    $\begingroup$ @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, $\endgroup$ – Markus Scheuer May 9 '15 at 22:49

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.