Lower bound for diagonal Ramsey numbers

Question

In the book "The Probabilistic Method" by Alon and Spencer there is a quite clear derivation (provided by Lovasz local lemma) of the fact, that if $ e\binom{k}{2}\binom{n-2}{k-2}\cdot 2^{1-\binom{k}{2}}<1 $, then $ R(k,k)>n $. Then authors write that "a short computation shows that this gives" $ R(k,k)>(\sqrt{2}/e)(1+o(1))k2^{k/2} $. To be honest, I completely don't understand how to prove it, because it seems that use of asymptotic equivalence will spoil initial inequality. I've seen the post (Asymptotic lower bound for R(k,k)), but I'm not sure that it answers my question.

Answer 1

Assuming $n>2k$, we have $$ \binom{n-2}{k-2} < \binom n{k-2} < \left( \frac{en}{k-2} \right)^{k-2} < e^2\left( \frac{en}{k} \right)^{k-2}, $$ where the middle (well-known) estimate follows from $$ \binom nm < \frac{n^m}{m!} = \left(\frac nm\right)^m \frac{m^m}{m!} < \left(\frac nm\right)^m \sum_{j=0}^\infty \frac{m^j}{j!} = \left( \frac{en}{m} \right)^m. $$ Therefore, $$ e \binom k2 \binom{n-2}{k-2} 2^{1-\binom k2} < e^3 k^2 \left( \frac{en}{k} 2^{-(k+1)/2} \right)^{k-2}. $$ It follows that if, say, $$ 2k < n < (\sqrt 2/e)k2^{k/2}(1-1/\log k), \tag{$\ast$} $$ then $$ e \binom k2 \binom{n-2}{k-2} 2^{1-\binom k2} < e^3 k^2 \left( 1-\frac1{\log k}\right)^{k-2} < e^3k^2 e^{-(k-2)/\log k} <1, $$ implying $R(k,k)>n$. The estimate in question is now obtained by choosing $n$ to be the largest integer in the range ($\ast$).