Sum of binomial coefficients so that the sum equals ${n\choose n/2}$

Question

I am trying to find $m$ (either exact or order of $m$ in terms of $n$) such that:

$$\sum_{k=0}^m\binom{n}{k} = {n\choose \frac{n}{2}}$$

I was thinking of applying Stirling's approximation for factorials for large $n$, so $\displaystyle\binom{n}{\frac{n}{2}}\sim\frac{2^n}{\sqrt{n}}$. But looking at $\displaystyle{n\choose k}=\frac{n!}{k!(n-k)!}$ and that the sum over $k$ starts from $k=0$, I cannot use Stirling's approximation for $k!$ for small $k$.

I was also looking at sum of binomial coefficients on Wiki which gives an upper bound for the sum and so am wondering if getting an upper bound is the best we can do or if we can find $m$ precisely?

Answer 1

This is an interesting problem from a numerical point of view.

Transposed in the real domain, you are looking for $m$ such that

$$\color{blue}{\frac{\, _2F_1(1,m-n+1;m+2;-1)}{\Gamma (m+2) \,\,\Gamma (n-m)} =\frac{2^n}{\Gamma (n+1)}-\frac{1}{\Big[\Gamma \left(\frac{n}{2}+1\right)\Big]^2}}$$ where $m$ and $n$ are real numbers.

This equation is not difficult to solve using Newton method with $m_0=\frac n 2$. This starting point is justified by the left part of the trivial double inequality $$\binom{n}{m} \leq\sum_{k=0}^m\binom{n}{k}\leq (m+1)\binom{n}{m}$$ which means that we already know that $m \leq \frac n 2$. I did not find any simple way to use the right part of the above inequality (this is no more true : have a look at the $\color{red}{\text{ update}}$) .

For example, for $n=10$, the iterates are $$\left( \begin{array}{cc} k & m_k \\ 0 & 5.000000000 \\ 1 & 3.419647982 \\ 2 & 3.407971414 \\ 3 & 3.407943361 \end{array} \right)$$

Below are some results (I let you rounding the results the way you want). $$\left( \begin{array}{cc} n & m \\ 10 & 3.40794 \\ 20 & 7.41879 \\ 30 & 11.5964 \\ 40 & 15.8702 \\ 50 & 20.2093 \\ 60 & 24.5969 \\ 70 & 29.0227 \\ 80 & 33.4793 \\ 90 & 37.9619 \\ 100 & 42.4665 \\ 110 & 46.9903 \\ 120 & 51.5309 \\ 130 & 56.0864 \\ 140 & 60.6554 \\ 150 & 65.2365 \\ 160 & 69.8287 \\ 170 & 74.4310 \\ 180 & 79.0426 \\ 190 & 83.6628 \\ 200 & 88.2910 \\ 210 & 92.9267 \\ 220 & 97.5694 \\ 230 & 102.219 \\ 240 & 106.874 \\ 250 & 111.535 \\ 260 & 116.202 \\ 270 & 120.874 \\ 280 & 125.550 \\ 290 & 130.232 \\ 300 & 134.918 \end{array} \right)$$

This looks to be very close to linearity. Using these numbers, a quick and dirty linear regression for $m=a +b \,n$ leads to $R^2=0.999957$ $$\begin{array}{clclclclc} \text{} & \text{Estimate} & \text{Standard Error} & \text{Confidence Interval} \\ a & -2.6778 & 0.2028 & \{-3.0938,-2.2618\} \\ b & +0.4561 & 0.0011 & \{+0.4538,+0.4585\} \\ \end{array}$$

Using this empirical model for $n=400$, it gives $m=179.775$ while the solution is $181.986$.

As I wrote in comments, this also works for non integer values of $n$. For $n=123.456$, $m=53.1037$.

Update

I managed to use $$\sum_{k=0}^m\binom{n}{k}\leq (m+1)\binom{n}{m}$$ defining the function $$f(m)=(m+1)\binom{n}{m}- {n\choose \frac{n}{2}}$$ which was expanded as a series to $O\left(\left(m-\frac{n}{2}\right)^3\right)$. Solving the quadratic, the approximate solution is given by $$m=\frac n 2-\frac{n}{1+\sqrt{n} \sqrt{(n+2) \psi ^{(1)}\left(\frac{n}{2}\right)-\frac{3 n+8}{n^2}}}$$ which is a much better starting point as shown below $$\left( \begin{array}{ccc} n & \text{approximation} & \text{solution} \\ 50 & 20.5142 & 20.2093 \\ 100 & 43.4413 & 42.4665 \\ 150 & 66.8507 & 65.2365 \\ 200 & 90.5099 & 88.2910 \\ 250 & 114.329 & 111.535 \\ 300 & 138.261 & 134.918 \end{array} \right)$$

The asymptotics of the approximation is $$m=\frac n2 \left(1-\sqrt{\frac 2 n}+\frac 1 n+O\left(\frac{1}{n^{3/2}}\right)\right)$$

Update

I found later this question; @user940 gave a very interesting asymptotic approximation. Adapted to your problem, we look for the solution $m$ of the equation $$2^{n-1} \left(1-\text{erf}\left(\frac{n-2 m}{\sqrt{2n} }\right)\right)=\binom{n}{\frac{n}{2}}$$ that is to say $$\text{erf}\left(\frac{n-2 m}{\sqrt{2n} }\right)=1-\frac{2\, \Gamma \left(\frac{n+1}{2}\right)}{\sqrt{\pi } \,\Gamma \left(\frac{n}{2}+1\right)}$$ This can be inversed using approximations of the error function (have a look here).

This would give $$\left( \begin{array}{cc} 50 & 20.7060 \\ 100 & 42.9608 \\ 150 & 65.7299 \\ 200 & 88.7840 \\ 250 & 112.028 \\ 300 & 135.410 \end{array} \right)$$ which is significantly better for large values of $n$.

Concerning the asymptotics of $n$, using $$\text{erf}(x)=1+e^{-x^2} \left(-\frac{1}{\sqrt{\pi } x}+O\left(\frac{1}{x^3}\right)\right)$$ we have $$m=\frac n 2-\frac {\sqrt n } 2 \sqrt{W(t)}\qquad \text{where} \qquad t=\frac 12\left(\frac{\Gamma \left(\frac{n+2}{2}\right)}{\Gamma \left(\frac{n+1}{2}\right)} \right)^2$$ $W(.)$ being Lambert function. So, as expected earlier, a logarithmic contribution in the asymptotics of $m$.