# Sum of the first k binomial coefficients for fixed n

I am reading Remarks on a Ramsey theory for trees by Janos Pach, Jozsef Solymosi and Gabor Tardos.

Let $k, d, n \geq 2$ be integers. Somethig interesting happens when $$2^{n/k} > \sum_{i=0}^{d-1} {n \choose i}$$ They say that it follows by straightforward computation that this inequality holds for $n > 5 d k \log_2 k$.

I do not know how to do this straightforward computation. I have read https://mathoverflow.net/questions/17202/sum-of-the-first-k-binomial-coefficients-for-fixed-n, but nothing there seems useful to me. I have tried substituting $n = 5 d k \log_2 k$ and some estimates.

What am I missing?

The RHS is $2^nP[X\lt d]$ where $X$ is binomial $(n,\frac12)$ and, for every $x$ in $(0,1)$, $$P[X\lt d]\leqslant x^{-d}E[x^X].$$ Since $E[x^X]=\left(\frac{1+x}2\right)^n$, the claim is proved as soon as there exists $x$ in $(0,1)$ such that $$(1+x)^n\lt2^{n/k}x^d.$$ Assume that $n\gt adk\log k$ for some given $a$ (in the question, $a=5/\log2$). Then it suffices to look at the case when $d$ is maximal, that is, to check that $$(1+x)^n\lt2^{n/k}x^{n/(ak\log k)}.$$ Equivalently, one asks that $$\left(1+x\right)^{ak\log k}\lt k^ax.$$ Assuming that $x=1/(ak\log k)$ and using the upper bound $1+x\lt\mathrm e^x$ for every $x\gt0$, one sees that this condition holds as soon as $$a\mathrm e\log k\leqslant k^{a-1}.$$ The function $u\mapsto u^{a-1}-a\mathrm e\log u$ is nondecreasing on $u\geqslant2$ if $(a-1)2^{a-1}\geqslant a\mathrm e$ hence this function is nonnegative on $u\geqslant2$ as soon as, furthermore, $2^{a-1}\geqslant a\mathrm e\log2$. These two conditions hold for every $a\geqslant3.865$ hence $a=5/\log2=7.213$ is allright but the factor $5$ in the question could be replaced by $2.1$.