1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.