How to go from this summation to this approximation?

Question

https://learn.fmi.uni-sofia.bg/pluginfile.php/194197/mod_resource/content/2/Telephone_numbers.pdf

I'm a high school student investigating on telephone numbers (involution numbers) depicted as T(n). If you read this link, you'll have a good understanding on what I'm talking about. Under the Mathematical Properties subheading in this pdf, there's a section on the summation formula and its approximation. I have no idea how this step works. It mentions that it uses Stirling's approximation. Anyone willing to help? For a certain n value (has to be a natural number) it says it goes from:

$\sum_{k=0}^{[n/2]} \frac{n!}{2^k(n-2k)!k!}$

to

$(\frac{n}{e})^{(\frac{n}{2})} \frac {e^\sqrt n}{(4e)^\frac{1}{4}}$

Note that the summation formula has [n/2], but that's because for odd numbers it's [(n-1)/2]. So if n=5 then k=2 is the largest k. Maybe it's easier to think of it through two separate formula's according to parity, one with [n/2] and another with [(n-1)/2]

I have no idea how the k disappears. Please help

Answer 1

The following holds: \begin{align*} T(n)=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{n!}{2^kk!(n-2k)!} \sim\frac{1}{\sqrt{2}}n^{\frac{n}{2}}\exp\left(-\frac{1}{2}n+n^{\frac{1}{2}}-\frac{1}{4}\right)\tag{1} \end{align*}

The validity of the asymptotic expansion (1) can be obtained in two steps:

• The first step is to derive an exponential generating function $\mathcal{T}(z)=\sum_{n=0}^\infty T(n)\frac{z^n}{n!}$.

• The generating function $\mathcal{T}(z)$ encodes the wanted information of the coefficients $T(n)$ which can be extracted using complex analytic methods. Here we can apply a technique from Hayman to obtain the analytic expansion.

We start with the first step which is in fact the easy part.

Exponential generating function $\mathcal{T}(z)$:

We obtain from the left-hand side of (1): \begin{align*} \color{blue}{\mathcal{T}(z)}&=\sum_{n=0}^\infty T(n)\frac{z^n}{n!}\\ &=\sum_{n=0}^\infty \sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\frac{1}{2^kk!(n-2k)!}z^n\tag{2.1}\\ &=\sum_{n=0}^\infty\sum_{{2k+l=n}\atop{k,l\geq 0}}\frac{1}{2^kk!l!}z^n\tag{2.2}\\ &=\sum_{k=0}^\infty\frac{z^{2k}}{2^kk!}\sum_{l=0}^\infty\frac{z^l}{l!}\tag{2.3}\\ &=\exp\left(\frac{z^2}{2}\right)\exp\left(z\right)\tag{2.4}\\ &\,\,\color{blue}{=\exp\left(\frac{z^2}{2}+z\right)}\tag{3} \end{align*}

Comment:

• In (2.1) we take $T(n)$ from (1) and cancel $n!$.

• In (2.2) we write the coefficient of the Cauchy product in the form $$\sum_{k=0}^n a_kb_{n-k}=\sum_{{k+l=n}\atop{k,l\geq 0}}a_kb_l$$

• In (2.3) we write the series as product of two series.

• In (2.4) we use the series expansion $e^z=\sum_{n=0}^\infty \frac{z^n}{n!}$.

Hayman's method:

We can now apply to the exponential generating function in (3) the technique published by Hayman (1956) to derive the asymptotic expansion in (1). This is shown in detail in this answer.

Notes:

• Some more detailed information regarding Hayman's method is given in chapter VIII.5 Admissibility in Analytic combinatorics by P. Flajolet and R. Sedgewick.

• A more general case was proven by H. S. Wilf in The Asymptotics of $e^{P(z)}$ and the number of elements of each order in $S_n$ from 1986. In this proof we can also find a nice application of the Lagrange inversion theorem.