I am trying to read The Probabilistic Method (for leisure, not for school) by Alon and Spencer, and I am having trouble seeing why a particular step is true:
In chapter 1 they prove that If ${n \choose k}$$(1-2^{-k})^{n-k}<1$, there is a tournament on $n$ vertices that has the property $S_k$. I understand how this theorem is proved, but the part after is unclear to me.
The text says "Let $f(k)$ denote the minimum possible number of vertices of a tournament that has the property $S_k$. Since ${n \choose k} < (en/k)^k$ and $(1-2^{-k})^{n-k}<e^{-(n-k)/2^k}$, the theorem above implies that $f(k) \leq k^2 \cdot 2^k \cdot ln(2)(1 + o(1))$."
I am having trouble verifying that the two bounds and the theorem imply this. In attempting to isolate $n$, it is not clear to be where some parts of the right-hand side of the inequality come from. I think it is because I do not really understand what it means to see $o(1)$ in a product like that. I think I would understand this better if I saw the steps worked out for where the $o(1)$ comes into play.
Can someone help me fill in these steps? Also, if anyone knows of any resources for learning about basic asymptotic analysis, that would help as well.
Since $\binom nk < (en/k)^k$ and $(1 - 2^{-k})^{n-k} < e^{-(n-k)/2^k}$, we have $$ \binom nk (1 - 2^{-k})^{n-k} < \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k}. $$ If we choose an $n$ to make the right-hand side less than $1$, then the left-hand side is also less than $1$, and we'll be able to conclude that $f(k) \le n$.
Here is some intuition for how we can get the expression in the book. First, we can rewrite all this by separating the really important terms from the less significant ones: $$ \left(\frac{en}{k}\right)^k e^{-(n-k)/2^k} = \frac{n^k}{e^{n/2^k}} \cdot \left(\frac ek\right)^k e^{k/2^k} = \frac{n^k}{e^{n/2^k}} \cdot \left(\frac{e^{1 - 1/2^k}}{k}\right)^k. $$ For $k>2$, the second factor here will be less than $1$, so we can ignore it, and just try to choose an $n$ for which $n^k < e^{n/2^k}$. Taking the natural logarithm of both sides, we get $k \ln n < n/2^k$, or $\frac{n}{\ln n} > k \cdot 2^k$. Let's set $t = k \cdot 2^k$, because we're going to be using that expression a bunch now.
The inverse of $y = \frac{x}{\ln x}$ is a lot like $x = y \ln y$ asymptotically, so let's try seeing what happens when $n = t \ln t$. Then $\frac{n}{\ln n} = \frac{t \ln t}{\ln t + \ln \ln t}$, which is not quite bigger than $t$, because $\frac{\ln t}{\ln t + \ln \ln t} < 1$. But we don't need a much bigger value of $n$: for example, if $n = t \ln t\left(1 + \frac{2 \ln \ln t}{\ln t}\right)$, then $$ \frac{n}{\ln n} = t \cdot \frac{\ln t (1 + \frac{2 \ln \ln t}{\ln t})}{\ln t + \ln \ln t + \ln(1 + \frac{2 \ln \ln t}{\ln t})} = t \cdot \frac{\ln t + \ln \ln t + \ln \ln t}{\ln t + \ln \ln t + \ln(1 + \frac{2 \ln \ln t}{\ln t})} $$ and because $\ln \ln t > \ln(1 + \frac{2 \ln \ln t}{\ln t})$ for sufficiently large $t$ (the left goes to infinity and the right goes to $0$), the numerator eventually exceeds the denominator, and so when $t$ is large, we get $\frac{n}{\ln n} > t$.
This is often glossed as saying that the inverse of $y = \frac{x}{\ln x}$ is $y \ln y(1 + o(1))$, because the factor of $1 + \frac{2 \ln \ln t}{\ln t}$ that we used is a $1+o(1)$ factor. Asymptotically inverting $\frac{x}{\ln x}$ is very often useful. This is something you'll eventually become quick at spotting if you do much more asymptotic analysis: the previous paragraph will become a single mental step.
Anyway, in order to get $\frac{n}{\ln n} > t$, we want to set $n = t \ln t (1 + o(1))$. In our case, $t = k \cdot 2^k$, and $t \ln t = k \cdot 2^k \cdot (k \ln 2 + \ln k) = k^2 \cdot 2^k \cdot \ln 2 \cdot (1 + \frac{\ln k}{k \ln 2})$. The factor of $(1 + \frac{\ln k}{k \ln 2})$ is another factor of $(1+o(1))$, which combines with the previous such factor to give us the final expression $f(k) \le k^2 \cdot 2^k \cdot \ln 2 \cdot (1 + o(1))$.