# 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!

• Maybe Stirling's Approximation helps? Aug 31, 2022 at 7:57
• Aug 31, 2022 at 8:19

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

• This proof shows the inequality for sufficiently large $n$ only, which seems to be enough for the OP though.
– Gary
Aug 31, 2022 at 12:11
• Thanks so much for this answer! I was actually looking for one that works for all $n$, but the Stirling's formula bound seems to suffice. If there's an obvious way to generalise the first bound here to to any $n$ case I'd love to see it. Aug 31, 2022 at 15:15
• @user138901. See my edit. It seems to be always true Aug 31, 2022 at 15:33
• +1 Kotesovec really has come up with bounds and asymptotics for so many wonderful series, it's very impressive. Sep 1, 2022 at 1:46

By $$(13.2.39)$$, $$(13.8.12)$$ and $$(10.30.4)$$ \begin{align*} {}_1F_1 (1 - n,2, - 1) &= \mathrm{e}^{ - 1} {}_1F_1 (n + 1,2,1) \sim \frac{1}{n}\sqrt {\frac{{n + 1}}{\mathrm{e}}} I_1 (2\sqrt {n + 1} ) \\ & \sim \frac{1}{n}\sqrt {\frac{{n + 1}}{\mathrm{e}}} \frac{{\mathrm{e}^{2\sqrt {n + 1} } }}{{2\sqrt {\pi \sqrt {n + 1} } }} \sim \frac{{\mathrm{e}^{2\sqrt {n + 1} } }}{{2n^{3/4} \sqrt {\mathrm{e}\pi } }} \sim \frac{{\mathrm{e}^{2\sqrt n } }}{{2n^{3/4} \sqrt {\mathrm{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{{\mathrm{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 $$\mathrm{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{{\mathrm{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{{\mathrm{e}^x }}{{\sqrt {2\pi x} }}\left( {1 + \frac{{R_1^{(K)} (x\mathrm{e}^{\pi \mathrm{i}} ,1) + R_1^{(K)} (x\mathrm{e}^{ - \pi \mathrm{i}} ,1)}}{2}} \right).$$ By Theorem $$1.2$$ of the paper, we have $$\frac{{R_1^{(K)} (x\mathrm{e}^{\pi \mathrm{i}} ,1) + R_1^{(K)} (x\mathrm{e}^{ - \pi \mathrm{i}} ,1)}}{2} \\ = - \frac{1}{{2\pi x}}\left( {\operatorname{Re} \Lambda _1 (2x\mathrm{e}^{\pi \mathrm{i}} ) + \int_0^{ + \infty } {\frac{{t^{ - 1} }}{{1 + t}}{\bf F}\!\left( {\tfrac{3}{2}, - \tfrac{1}{2};0; - t} \right)\operatorname{Re} \Lambda _1 (2x\mathrm{e}^{\pi \mathrm{i}} (1 + t))\mathrm{d}t} } \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, $$\operatorname{Re} \Lambda _1 (w\mathrm{e}^{\pi \mathrm{i}} ) = - w\mathrm{e}^{ - w} \operatorname{Re} \Gamma (0,w\mathrm{e}^{\pi \mathrm{i}} ) = - w\mathrm{e}^{ - w} \operatorname{Re} E_1 (w\mathrm{e}^{\pi \mathrm{i}} ) = w\mathrm{e}^{ - w} {\mathop{\rm Ei}\nolimits} (w) > 0$$ for any $$w\geq 1$$. This proves the bound for $$x\geq \frac{1}{2}$$. For $$0, we note that $$I_1 (x) < I_1 \left(\tfrac{1}{2}\right) < 0.26 < \frac{{\mathrm{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{{\mathrm{e}^{2\sqrt {n - 1} } }}{{2(n - 1)^{3/4} \sqrt \pi }} \le \frac{{\mathrm{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} \mathrm{e}^{2x}$$ is increasing for $$x\geq 1$$. For $$n=1$$, the inequality may be checked by simple numerical computation.