1
$\begingroup$

How do you prove $\lim_{k\to\infty,k\in\mathbb{N}}{n\choose k}2^{1-{k\choose2}}=1$, where $n=\max\{n\in\mathbb{N}:{n\choose k}2^{1-{k\choose2}}<1\}$? The expression ${n\choose k}2^{1-{k\choose2}}$ comes up in a lower bound for the Ramsey number $R(k,k)$, and I want to fill in the steps in the derivation of the asymptotics of $n$.

I have tried playing around with identities like $${m\choose k+1}2^{1-{k+1\choose2}}=\frac{m-k}{k+1}2^{-k}{m\choose k}2^{1-{k\choose2}}$$ and $${m+1\choose k+1}2^{1-{k+1\choose2}}=\frac{m+1}{m-k}{m\choose k+1}2^{1-{k+1\choose2}},$$ but I didn't get anywhere.

Spencer, Joel, Ten lectures on the probabilistic method., CBMS-NSF Regional Conference Series in Applied Mathematics. 64. Philadelphia, PA: SIAM, Society for Industrial and Applied Mathematics. vi, 88 p. (1994). ZBL0822.05060.

$\endgroup$
0

1 Answer 1

4
$\begingroup$

Let $N(k) = \max \{n \in \mathbb N: \; {n \choose k} 2^{1-{k\choose 2}} < 1 \}$. Note that $$\frac{{n+1 \choose k}}{{n \choose k}} = \frac{n+1}{n+1-k}$$ so it suffices to prove that $N(k)/k \to \infty$ as $k \to \infty$. But for any finite $c > 1$, $$ \log {c k \choose k} \sim (c \log c - (c-1) \log (c-1)) k = o(k^2)$$ so $$ {c k \choose k} 2^{1 - {k \choose 2}} \to 0 \ \text{as}\ k \to \infty$$ and thus for sufficiently large $k$ we must have $N(k) > c k$.

$\endgroup$
3
  • $\begingroup$ Okay, why does $N(k)/k\to\infty$ suffice? $\endgroup$ Jun 29, 2018 at 18:03
  • $\begingroup$ We have $k^3/k=k^2\to\infty$ but ${k^3\choose k}2^{1-{k\choose2}}\to0\neq1$, if I'm not mistaken; the condition doesn't seem to suffice for this case. $\endgroup$ Jun 29, 2018 at 20:41
  • 1
    $\begingroup$ Let $f(n,k) = {n \choose k} 2^{1-{k \choose 2}}$. The point is that by definition, $$ f(N(k),k) < 1 \le f(N(k)+1,k) = \frac{N(k)+1}{N(k)+1-k} f(N(k),k)$$ so if $N(k)/k \to \infty$, $0 < 1 - f(N(k),k) \le \frac{k}{N(k)+1-k}f(N(k),k) \to 0$. $\endgroup$ Jun 29, 2018 at 20:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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