Using:
- ${k \choose 2} \leq \frac{k^2}{2}$, and
- ${{n-2} \choose {k-2}} \leq \frac{k^2}{n^2}{n \choose k} \leq \frac{k^2}{n^2} \left(\frac{ne}{k}\right)^k$,
we have $e2^{1 - {k \choose 2}}{k \choose 2}{{n-2} \choose {k-2}} \leq \frac{e2^{-{k \choose 2}}k^4}{n^2} \left( \frac{ne}{k} \right)^k = \frac{ek^4}{n^2} \left( \frac{ne \sqrt2}{k{\sqrt2}^k} \right) ^k$.
If $n=\frac{1}{e \sqrt{2}} k \sqrt{2}^{k},$ the parenthetical term is 1. The leading coefficient is then $e^{2} k^{2} 2^{1-k}$.
Now the text I'm reading says that we can afford for the parenthetical term to be $2 + o(1)$, and so we can take $ n=\left(\frac{\sqrt{2}}{e}+o(1)\right) k \sqrt{2}^{k}$. Can I get an explanation of these last two assertions?
This expression looks like some sort of Ramsey Theory construction. The goal is to find the largest $n = n(k)$ such that the inequality holds in the limit $k \to \infty$, I presume.
Suppose that in $n = \left(\frac{\sqrt{2}}{e} + o(1)\right) k \sqrt{2}^k$, we take the $o(1)$ term to be say, $\frac{\sqrt{2}}{ek}$, forcing the parenthetical term to be, $2 - 2/\sqrt{k}$. Then the exponential term is now $$\left(2 - \frac{2}{\sqrt{k}}\right)^k = 2^k \left(1 - \frac{1}{\sqrt{k}}\right)^k \sim 2^k e^{-\sqrt{k}}$$ Note that the factor of $2^{-k}$ brought about by the factor of $1/n^2$ outside the exponent will cancel the $2^k$ from the exponent, and asymptotically the expression will grow like $k^2 e^{-\sqrt{k}}$, which is certainly $o(1)$.
The idea is that if the exponential term grows slow enough than $2^k$, then the factor of $1/n^2$ can cancel this growth as it has a factor of $2^{-k}$. In the above example, we've shown that this can be obtained by having the base of the exponent to be $2 - o(1)$.