1
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ There certainly isn’t a value $m$ for all $n$ with exact equality. $\endgroup$ Nov 18, 2020 at 4:07
  • $\begingroup$ @ThomasAndrews True, I guess I am looking for the order of $m$ in terms of $n$ then. $\endgroup$ Nov 18, 2020 at 4:10
  • $\begingroup$ @ThomasAndrews. It is OK in the real domain. $\endgroup$ Nov 18, 2020 at 11:16
  • $\begingroup$ Improved using the upper bound. $\endgroup$ Nov 21, 2020 at 9:33

1 Answer 1

2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ How does a $c$ of $1.04$ (or an $m=a+bn\log n$ model, as you suggest) even make sense in your last model? It means you'd have $m\gt n$ for sufficiently large $n$... $\endgroup$ Nov 19, 2020 at 5:18
  • $\begingroup$ @StevenStadnicki. If you look at my last update, you will see that the asymptotics of $m$ contains a logarithmic contribution because of Lambert function. $\endgroup$ Nov 28, 2020 at 9:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .