Bounding this Summation of Binomials and Factorials

Question

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!

Answer 1

Consider $$a_n=n! \,\, _1F_1(1-n;2;-1)$$ which generates sequence $A000262$ in $OEIS$

In the formula section, you will see the asymptotics given by Vaclav Kotesovec in year $2013$. Using it

$$\, _1F_1(1-n;2;-1)\sim \frac{n^{n-\frac{1}{4}}}{n!\sqrt{2e}}\,e^{2 \sqrt{n}-n} \left(1-\frac{5}{48 \sqrt{n}}-\frac{95}{4608 n}+O\left(\frac{1}{n^{3/2}}\right)\right) \tag 1$$

Computing for $n=20000$ the exact value is $6.98525619\times 10^{118}$ while the approximation gives $6.98525623\times 10^{118}$

So, a good and simple upper bound is $$\, _1F_1(1-n;2;-1) < \frac{n^{n-\frac{1}{4}}}{n!\sqrt{2e}}\,e^{2 \sqrt{n}-n} $$ The expansion is also an upper bound.

Edit

Using Stirling approximation, we have the simpler

$$\, _1F_1(1-n;2;-1) < \frac {e^{2 \sqrt{n}} } {2 n^{\frac 34}\sqrt{e \pi } }$$

A few values to compare the formula $(1)$ anf the exact value $$\left( \begin{array}{cccc} n & (1) & \, _1F_1(1-n;2;-1) & (1)-\, _1F_1(1-n;2;-1) \\ 1 & 1.02035 & 1.00000 & 0.0203472 \\ 2 & 1.51288 & 1.50000 & 0.0128769 \\ 3 & 2.17622 & 2.16667 & 0.0095515 \\ 4 & 3.04968 & 3.04167 & 0.0080102 \\ 5 & 4.18230 & 4.17500 & 0.0073022 \\ 6 & 5.63344 & 5.62639 & 0.0070493 \\ 7 & 7.47395 & 7.46687 & 0.0070821 \\ 8 & 9.78790 & 9.78058 & 0.0073181 \\ 9 & 12.6746 & 12.6669 & 0.0077157 \\ 10 & 16.2508 & 16.2426 & 0.0082544 \end{array} \right)$$

Answer 2

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.