Show $\binom{\lceil 2^{\frac{k}{2}} \rceil }{k} \leq 2^{\binom{k}{2} - 1}$ for $k \geq 2$

Question

Show $\binom{\lceil 2^{\frac{k}{2}} \rceil }{k} \leq 2^{\binom{k}{2} - 1}$ for $k \geq 2$ .

The proof which I am studying uses the above result to show that $R(k,k) < \lceil 2^{\frac{k}{2}} \rceil$ where $R$ denotes the Ramsay number. I cannot see how to prove the inequality: induction doesn't work, is there some upper bound inequality on binomial coefficients which I am missing?

Answer 1

The latex is a little ambiguous but I assume you are referring to $2^{k/2}=(\sqrt{2})^k.$

In general $\binom{n}{k}\leq \frac{n^k}{k!}$. Thus, $$ \binom{\lceil \sqrt{2}^{k}\rceil}{k}\leq \frac{\lceil \sqrt{2}^{k}\rceil^k}{k!}. $$ Hence the inequality will follow once we show that $$ \lceil \sqrt{2}^{k}\rceil^k\leq k!\ 2^{\binom{k}{2}-1}. $$ Now $\lceil \sqrt{2}^{k}\rceil\leq \sqrt{2}^k+1$, and thus it suffices to establish that $$ (\sqrt{2}^k+1)^k\leq k!\ 2^{\binom{k}{2}-1}. $$ Since $k!\geq 2^{k-1}$, it suffices to show that $$ (\sqrt{2}^k+1)^k\leq 2^{\binom{k}{2}+k-2}. $$ Pulling out $2^{k^2/2}$ from the left sides yields the equivalent inequality $$ (1+2^{-k/2})^k\leq 2^{k/2-2}, $$ and taking $k^{th}$ roots yields the equivalent inequality $$ 1+2^{-k/2}\leq 2^{1/2-2/k}. $$ This inequality holds for all $k\geq 7$, since $$ 1+2^{-k/2}\leq 1+2^{-7/2}<2^{1/2-2/7}\leq 2^{1/2-2/k}\qquad k\geq 7. $$ The cases $k=2,\ldots,6$ can be verified directly in the original inequality.

Answer 2

I completed the proof for odd $k$, so here's the whole thing.

$\binom{\lceil 2^{\frac{k}{2}} \rceil }{k} \leq 2^{\binom{k}{2} - 1} $

The RHS is $2^{k(k-1)/2-1} =2^{(k^2-k-2)/2} =2^{(k-2)(k+1)/2} $.

If $k = 2m$, the LHS is

$\begin{array}\\ \binom{\lceil 2^{m} \rceil }{2m} &=\binom{ 2^{m} }{2m}\\ &=\dfrac{\prod_{j=0}^{2m-1}(2^m-j)}{(2m)!}\\ &\lt\dfrac{\prod_{j=0}^{2m-1}(2^m)}{(2m)!}\\ &=\dfrac{2^{2m^2}}{(2m)!}\\ \end{array} $

so we would like

$\dfrac{2^{2m^2}}{(2m)!} \lt 2^{(4m^2-2m-2)/2} = 2^{2m^2-m-1} $ or $(2m)! \gt 2^{m+1} $ and this is clearly true.

If $k = 2m+1$, the LHS is

$\begin{array}\\ \binom{\lceil 2^{m+1/2} \rceil }{2m+1} &=\dfrac{\prod_{j=0}^{2m}(\lceil 2^{m+1/2} \rceil -j)}{(2m)!}\\ &=\dfrac{\lceil 2^{m+1/2} \rceil\prod_{j=1}^{2m}(\lceil 2^{m+1/2} \rceil -j)}{(2m)!}\\ &\le\dfrac{\lceil 2^{m+1/2} \rceil\prod_{j=1}^{2m}(\lceil 2^{m+1/2} \rceil -1)}{(2m)!}\\ &\lt\dfrac{(2^{m+1/2}+1)(2^{m+1/2})^{2m}}{(2m)!}\\ &=\dfrac{(2^{m+1/2}+1)2^{2m^2+m}}{(2m)!}\\ \end{array} $

and the RHS is

$\begin{array}\\ 2^{((2m+1)^2-(2m+1)-2)/2} &=2^{(4m^2+4m+1-2m-1-2)/2}\\ &=2^{(4m^2+2m-2)/2}\\ &=2^{2m^2+m-1}\\ \end{array} $

so we would like

$\dfrac{(2^{m+1/2}+1)2^{2m^2+m}}{(2m)!} \le 2^{2m^2+m-1} $ or $(2m)! \ge 2(2^{m+1/2}+1) $

and this is also clearly true.