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

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

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

It can be proven easily, that if $\beta > 2$, then

$$\beta^{-n} \sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k} \underset{n\to\infty}{\to} 0$$

so the task is not trivial. My numerical observations suggest that the conjecture is still true, and some beta from the interval $1 < \beta < 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

$$\sum_{k=0}^{[\alpha\cdot n]} \binom{n}{k}$$

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

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

Looks very smart!

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

$$n! \approx \sqrt{2\pi n}\Big(\frac{n}{e}\Big)^n$$

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

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

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

$$1 < \beta < \big(\alpha^{\alpha} (1-\alpha)^{1-\alpha}\big)^{-1}$$

Then

$$\beta^{-n}\binom{n}{[\alpha\cdot n]} \to \infty$$

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