Bounding this Summation of Binomials and Factorials I have the sum
$$\sum_{k=1}^n \binom{n-1}{k-1}\frac{1}{k!} =\ _1F_1(1 - n, 2, -1),$$
which I need to upper bound. Here $_1 F_1$ is the hypogeometric function.
I could trivially bound this as
$$\sum_{k=1}^n \binom{n-1}{k-1}\frac{1}{k!}\leq\sum_{k=1}^n \binom{n-1}{k-1} = 2^{n-1} $$ however this isn't tight enough for my purposes.
Plotting the function for $n<20,000$ seems to show that it doesn't scale exponentially, which leads me to think this is not tight.
I'm hoping there might be a quasi-polynomial bound $O(2^{polylog(n)})$ but don't see a way of proving this. Any help or suggestions on how to find an upper bound for this sum would be appreciated!
 A: By $(13.2.39)$, $(13.8.12)$ and $(10.30.4)$
\begin{align*}
{}_1F_1 (1 - n,2, - 1) &= e^{ - 1} {}_1F_1 (n + 1,2,1) \sim \frac{1}{n}\sqrt {\frac{{n + 1}}{e}} I_1 (2\sqrt {n + 1} ) \\ & \sim \frac{1}{n}\sqrt {\frac{{n + 1}}{e}} \frac{{e^{2\sqrt {n + 1} } }}{{2\sqrt {\pi \sqrt {n + 1} } }} \sim \frac{{e^{2\sqrt {n + 1} } }}{{2n^{3/4} \sqrt {e\pi } }} \sim \frac{{e^{2\sqrt n } }}{{2n^{3/4} \sqrt {e\pi } }}
\end{align*}
as $n\to +\infty$. Here $I_1$ is the modified Bessel function. Note that ${}_1F_1 (a,b,z) = M(a,b,z) = \Gamma (b){\bf M}(a,b,z)$ for $b\neq 0,-1,-2,\ldots$.
Addendum. I shall prove that
$$
\sum\limits_{k = 1}^{n} \binom{n - 1}{k-1}\frac{1}{{k!}} \le \frac{{e^{2\sqrt n } }}{{2n^{3/4} \sqrt \pi  }}
$$
for any $n\geq 1$. By the above asymptotic result, this is asymptotically sharp up to a constant factor (the extra $e^{-1/2}$ is missing on the right-hand side). I will use the following lemma. (In fact, we need it only for $x\geq 1$.)
Lemma. We have
$$I_1 (x) < \frac{{e^x }}{{\sqrt {2\pi x} }}$$
for any $x> 0$.
Proof. I shall use the results and notation of this paper. Assuming that $x>0$ and taking the average of the two versions of $(95)$ in that paper, we find
$$
I_1 (x) = \frac{{e^x }}{{\sqrt {2\pi x} }}\left( {1 + \frac{{R_1^{(K)} (xe^{\pi i} ,1) + R_1^{(K)} (xe^{ - \pi i} ,1)}}{2}} \right).
$$
By Theorem $1.2$ of the paper, we have
$$
\frac{{R_1^{(K)} (xe^{\pi i} ,1) + R_1^{(K)} (xe^{ - \pi i} ,1)}}{2} \\ =  - \frac{1}{{2\pi x}}\left( {\Re \Lambda _1 (2xe^{\pi i} ) + \int_0^{ + \infty } {\frac{{t^{ - 1} }}{{1 + t}}{\bf F}\!\left( {\tfrac{3}{2}, - \tfrac{1}{2};0; - t} \right)\Re \Lambda _1 (2xe^{\pi i} (1 + t))dt} } \right)
$$
for any $x>0$. By $(61)$ of the paper, ${\bf F}\!\left( {\frac{3}{2}, - \frac{1}{2};0; - t} \right) \ge 0$ for any $t>0$. We also have, using the incomplete gamma function and the exponential integrals,
$$
\Re \Lambda _1 (we^{\pi i} ) =  - we^{ - w} \Re \Gamma (0,we^{\pi i} ) =  - we^{ - w} \Re E_1 (we^{\pi i} ) = we^{ - w} {\mathop{\rm Ei}\nolimits} (w) > 0
$$
for any $w\geq 1$. This proves the bound for $x\geq \frac{1}{2}$. For $0<x<\frac{1}{2}$, we note that
$$
I_1 (x) < I_1 \left(\tfrac{1}{2}\right) < 0.26 < \frac{{e^x }}{{\sqrt {2\pi x} }}.
$$
This completes the proof. $\; \blacksquare$
Proof of the inequality. We have
\begin{align*}
\sum\limits_{k = 1}^{n} \binom{n - 1}{k-1}\frac{1}{{k!}} & = \sum\limits_{k = 0}^{n - 1} \binom{n - 1}{k}\frac{1}{{(k + 1)!}}  \le \sum\limits_{k = 0}^{n - 1} {\frac{{(n - 1)^k }}{{k!}}\frac{1}{{(k + 1)!}}} \\ & \le \sum\limits_{k = 0}^\infty  {\frac{{(n - 1)^k }}{{k!}}\frac{1}{{(k + 1)!}}}  = \frac{1}{{\sqrt {n - 1} }}I_1 (2\sqrt {n - 1} ) \\ & \le \frac{{e^{2\sqrt {n - 1} } }}{{2(n - 1)^{3/4} \sqrt \pi  }} \le \frac{{e^{2\sqrt n } }}{{2n^{3/4} \sqrt \pi  }},
\end{align*}
for $n\geq 2$, using the lemma and the fact that $x^{-3/4} e^{2x}$ is increasing for $x\geq 1$. For $n=1$, the inequality may be checked by simple numerical computation.
