Binomial coefficients sum conjecture about exponential

[jostpuur]

Fix some constant 0<\alpha \leq 1, and denote the floor function by x\mapsto [x]. The conjecture is that there exists a constant \beta > 1 such that

<br /> \beta^{-n} \sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k} \underset{n\to\infty}{\nrightarrow} 0<br />

Consider this conjecture as a challenge. I don't know how to prove it myself.

It can be proven easily, that if \beta &gt; 2, then

<br /> \beta^{-n} \sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k} \underset{n\to\infty}{\to} 0 <br />

so the task is not trivial. My numerical observations suggest that the conjecture is still true, and some beta from the interval 1 &lt; \beta &lt; 2 can be found so that the claim becomes true.

 

[micromass]

So, we know that for large n

\binom{n}{[\alpha n]}\sim \left(\frac{n}{\alpha n}\right)^{\alpha n}=\left(\alpha^{-\alpha}\right)^n

So take \beta\sim\alpha^{-\alpha}, and we get

\beta^{-n}\binom{n}{[\alpha n]}\rightarrow 1.

 

[jostpuur]

I thought that this would be a difficult problem because I saw no way to approximate the quantity

<br /> \sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k}<br />

I see that you decided to prove the result like this:

<br /> \Big( \beta^{-n}\binom{n}{[\alpha\cdot n]}\nrightarrow 0\Big)\quad\implies\quad\Big( \beta^{-n}\sum_{k=0}^{[\alpha\cdot n]}\binom{n}{k} \nrightarrow 0\Big)<br />

Looks very smart!

I encountered some difficulty when trying to check some details from your equations. When I substituted the approximation

<br /> n! \approx \sqrt{2\pi n}\Big(\frac{n}{e}\Big)^n<br />

and the approximation [\alpha\cdot n]\approx \alpha\cdot n, I got

<br /> \binom{n}{[\alpha\cdot n]} \approx \frac{1}{\sqrt{2\pi \alpha (1-\alpha)}} \frac{1}{\sqrt{n}}<br /> \Big(\alpha^{\alpha} (1-\alpha)^{1-\alpha}\Big)^{-n}<br />

So it looks like that the choice should be made so that

<br /> 1 &lt; \beta &lt; \big(\alpha^{\alpha} (1-\alpha)^{1-\alpha}\big)^{-1}<br />

Then

<br /> \beta^{-n}\binom{n}{[\alpha\cdot n]} \to \infty<br />

Convergence to somewhere between zero and infinity looks like impossible.

 

[micromass]

Hmm, I did not use Stirlings approximation actually, I used the approximation

\left(\frac{n}{k}\right)^k\leq \binom{n}{k}

But anyways, you're probably right that convergence to an actual number between 0 and infinity is impossible..