# A good estimate for a binomial sum

Are there good estimate for the sums

$$1.\quad\quad\quad\quad\quad\sum_{i=1}^k\frac{\binom{2k}{i}}{i!}$$

$$2.\quad\quad\quad\quad\quad\sum_{i=1}^k\frac{\binom{2k}{i}\binom{2k}{2k-i}}{i!(2k-i)!}=\sum_{i=1}^k\frac{\big(\binom{2k}{i}\big)^2}{i!(2k-i)!}$$

in the form of $$e^{f(k)}$$ where $$f(k)$$ is a suitable function of $$k$$?

• look at the largest term and apply Stirling's formula. For instance, for 1. you can take $f(k)=\sqrt{8k}$. – Henri Cohen Jun 16 '20 at 10:53
• $\sqrt{8}$ factor? ok. – VS. Jun 16 '20 at 10:55
• Henri Cohen's comment tells you how to get started. Almost always with binomial sums the number of summands is far less than the contribution from the largest summand, and the largest summand alone often gives a good asymptotic estimate. – Mark Wildon Jun 16 '20 at 11:55
• Mathematica finds an asymptotics for the logarithm of the first sum, resulting in $$\text{log}\left[-1+\frac{e^{-2 \sqrt{2} \sqrt{k}-\frac{1}{2}} \left(e^{4 \sqrt{2} \sqrt{k}} \left(48 \sqrt{2} \sqrt{k}+31\right)-48 i \sqrt{2} \sqrt{k}+31 i\right)}{96\ 2^{3/4} \sqrt{\pi } k^{3/4}}\right],$$ and this is confirmed numerically. – user64494 Jun 16 '20 at 18:12

For the first sum : For large $$k$$ the sum's summands have a single sharp maximum at $$\sqrt{2 k}$$ (up to $$O((2k)^{0})$$). This can be seen, e.g., by equating the ratio of the summands for $$i$$ and $$i+1$$ to 1. The summand is approximated by a Gaussian function and the sum is approximated by an integral over that Gaussian function.

For this write the summand as exponential, approximate the exponent in terms of logarithms of $$\Gamma$$-functions and exploit Stirlings formula for large arguments of $$\Gamma$$-functions. For $$i$$ insert $$\sqrt{2 k}+\tau$$ and expand the exponent up to second order in $$\tau$$ leading to said Gaussian. The sum over $$i$$ can be transformed in an integral over $$\tau$$. It does no harm to extend the integral limits from $$\tau=-\infty$$ to $$\tau=+\infty$$. Only an exponentially small error will be made. The Gaussian integral is readily calculated. Finally the result is expanded to order $$O((2k)^{-1/2})$$. The final result is: $$\sum_{i=1}^{k} \frac{{2 k} \choose i}{i!}\sim e^{2 \sqrt{2k}-\frac{1}{2}} k^{-1/4} \pi^{-{1/2}}2^{-5/4}$$ The error for $$k$$ as small as 5 is already only about 6%. It is exactly the exponentially dominant part of the result mentioned in user64494's comment.

The second sum is somewhat easier since one immediately sees that the summand is symmetric around $$i=k$$, which is also its maximum. The maximum is very sharp for large $$k$$. One can exploit exactly the same recipe as for the first sum, only that one takes only half of the Gaussian integral into account, since the maximum lies at the edge of the summation (The Gaussian is symmetric around $$\tau=0$$) The result is $$\sum_{i=1}^{k} \frac{{2 k} \choose i}{i!} \frac{{2 k} \choose {2 k-i}}{(2k-i)!}\sim e^{2k} k^{-2k-\frac{3}{2}}\pi^{-{3/2}} 3^{-1/2} 2^{-2+4 k}$$ The error is about 12% for $$k=50$$.

Edit: The error of the second sum can be reduce considerably by making use of Euler-Maclaurin. The conversion of the sum to an integral underestimates the contribution at the summation limits. Euler-Maclaurin suggests adding half of the value of the summand for $$i=k$$. This somewhat overshoots a bit, but reduces the absolute relative errors to about a quarter of the original ones. The contribution of the lower limit can still be neglected, though. It is exponentially small.

In the approximation of the first sum both ends of the summation exponentially small.

• My guess is for these error do not exceed $50\%$ even at $k\rightarrow\infty$ correct? – VS. Jun 19 '20 at 13:02
• The errors (=1 - asymptotic value /exact value) monotonically decrease for increasing $k$. So the error for the first asymptotic formula is always less than 6% for $k \ge 5$. For the second asymptotic formula it is less than 26 % (12 %) for $k \ge 5$ ($k \ge 50$). – Johannes Trost Jun 19 '20 at 13:08
• I mean what I am asking is if Striling type estimation is the best estimate for a 'natural' sum or product then is $50\%$ upper bound? – VS. Jun 19 '20 at 13:09
• @VS I am very sorry, but I am afraid, I do not understand your second question. Can you please rephrase the question ? Do you mean any general sum or product over the naturals can be approximated by the discribed method with error at most 50 % ? For this I would not know an answer, but I doubt it. – Johannes Trost Jun 19 '20 at 13:45