Upper bound for $\sum_{i=0}^k {k \choose i} \frac{k^i}{i!}$

Question

I need to find a good upper bound for the following sum:

$$ S_k = \sum_{i=0}^k {k \choose i} \frac{k^i}{i!}. $$

I manage to show that $S \leq poly(k)\cdot \gamma^k$, for some constant $\gamma$, by just replacing each of the summands by the largest one. It is not hard to see that the $\gamma$ obtained from this method far from being tight. I would like to get a tight bound for it, but I do not care about losing $poly(k)$ factors. Is it possible?

My original sum looked like $$ S_k' = \sum_{i=0}^k \frac{1}{((k-i)!)^2i!k^i} = \frac{1}{k^kk!} S_k, $$ which I modified to the above for a nicer presentation and the hope that the binomial coefficients could help.

Thank you!

Answer 1

$S_k$ is the coefficient of $x^k$ in $(1+x)^k e^{kx}$ (expanded into power series). We have $$S_k=\frac{1}{2\pi i}\oint_C\left[e^z\left(1+\frac{1}{z}\right)\right]^k\frac{dz}{z}$$ with $C$ encircling $z=0$. The saddle-point method gives the best value of your $$\gamma=\color{blue}{\frac{3+\sqrt{5}}{2}\exp\frac{\sqrt{5}-1}{2}}\approx 4.857$$ (and more elaborate asymptotics if needed).

Answer 2

This is not a complete answer, for it gives the first term in an asymptotic expansion. Remarks will be made on how to turn it into a bound.

$S_n$ can be written as $L_n(-n)$ where $L_n(x)$ is the Laguerre polynomial. Use a generating function for the Laguerre polynomials to get

$$L_n(-n) = \frac{1}{2\pi i} \oint \exp\big(-n(w/(w-1)+ (1+1/n)\log(w) \big))\frac{dw}{1-w} $$ The path is a circle of radius < 1 that encircles the origin. We'll do saddle point (SP) analysis. There are two SP which can be solved explicitly in terms of square roots. As we are interested in the $n \to \infty$ situation, we'll expand them as such: $$ \frac{d}{dw} h(w)\Big|_{w\to\tau} = 0 \implies \tau = (\frac{3}{2} -\frac{ \sqrt{5}}{2})\Big(1+\frac{1}{\sqrt{5}n}+\cal{O}(n^{-2}) \Big) $$ where $h(w)=w/(w-1)+(1+1/n)\log{w}.$ Since the leading factor is 0.381966.. and is positive, while the second SP is negative, it is clear this is the only SP we need to consider. Deform the contour through the SP. Furthermore, instead of a loop, we'll make it a vertical line, $w=\tau+i\ u$ where $u$ will be our integration variable.

$$L_n(-n) \sim \frac{1}{2\pi i} \int \exp\big(-n( h(\tau) + \tfrac{1}{2}h''(\tau)(w-\tau)^2))\frac{dw}{1-w} $$ $$ \quad \quad =\frac{1}{2\pi i} \exp\big(-n \ h(\tau) ) \int_{-\infty}^{\infty} \exp\big( \frac{n}{2}h''(\tau)u^2 \big) \frac{i \ du}{1-\tau-iu}$$ Let $a:= -\frac{n}{2}h''(\tau) = n\sqrt{5}/(2\ \mu^4)$ where $\mu = (\sqrt{5} -1)/2 $ and the expansion for $a$ in inverse powers of $n$ has stopped at the leading term. It is important that $a>0.$ Use the well-known integral

$$\int_{-\infty}^{\infty} \exp\big(-a\ u^2 \big) \frac{du}{u+ic} = -i \ \pi \ \text{sign}(c) e^{a\ c^2} \text{erfc}(\sqrt{a} |c| )$$ where $c$ is real and $a>0.$ Therefore $$ L_n(-n) \sim \frac{1}{2} \exp\big(-n \ h(\tau) ) e^{a\ \mu^2} \text{erfc}(\sqrt{a} \mu ) $$ It is now time to asymptotically expand some more expressions. It is well-known that $$ e^{x} \text{erfc}(\sqrt{x}) \sim \frac{1}{\sqrt{\pi \ x} } $$ It is tedious to show that $$ -h(\tau) = \mu - 2\log{\mu} - \frac{2}{n} \log{\mu} + \cal{O}(n^{-2}).$$ Collecting everything $$ L_n(-n) \sim \frac{\exp{\big(n(\mu - 2\log{\mu})\big)}}{\mu \sqrt{2\ \pi\ n \ \sqrt{5} } } \approx \frac{.431673}{\sqrt{n}} \exp{ (1.58046 \ n)} $$

To make this a bound, you have to go another order. That means another order in $n$ for the SP, for the correction term to the exponential (only the first 2 taylor terms have been done so far), and for the error function expansion. Collect all this, and you should get a formula that looks like

$$ L_n(-n) \sim \frac{\exp{\big(n(\mu - 2\log{\mu})\big)}}{\mu \sqrt{2\ \pi\ n \ \sqrt{5} } } \Big(1 + \frac{C_1}{n} \Big) $$

If $C_1$ <0, then you have proven that the first term in the asymptotic expansion is a bound for $n$ large enough. This is left as an exercise for the masochistic reader.

I did check the proposed formula for n up to 200, and it does indeed appear to be a bound. The asympotic term exceeds the brute force sum by 0.31% for n=20, 0.031% for n=200, and .0031% for n=2000. The largest error occurs for n=1, of course, and that differs by less that 5%.