Log inequalities and asymptotic expansions

Question

I'm dealing with the probabilistic method and how it applies to distinct sums. In the notes I'm using I encounter the following inequality:

$2^k\le nk$, which the notes simplify into this form:

$k\le \log_2n +\log_2\log_2n + O(1)$, and I have no idea how this is arrived at.

Clearly taking a $\log_2$ on both sides gives $\log_2 2^k\le \log_2 nk \implies k\le \log_2 n +\log_2 k$

But how do we get from $\log_2k$ to $\log_2\log_2n + O(1)$?

I'm sure I'm missing something obvious but any help would be appreciated.

Answer 1

Take the $\log_2$ of the initial inequality: $$ k \le \log _2 n + \log _2 k. $$ Taking the $\log_2$ again gives $$ \log _2 k \le \log _2 (\log _2 n + \log _2 k) = \log _2 \log _2 n + \log _2 \left( {1 + \frac{{\log _2 k}}{{\log _2 n}}} \right). $$ Substituting this back into the first inequality gives $$ k \le \log _2 n + \log _2 \log _2 n + \log _2 \left( {1 + \frac{{\log _2 k}}{{\log _2 n}}} \right). $$ Thus, it remains to show that the last term is $\mathcal{O}(1)$. But $$ k \le \log _2 n + \log _2 k \le \log _2 n + \frac{k}{2} \Rightarrow k \le 2\log _2 n \Rightarrow \log _2 k \le 2\log _2 n $$ whenever $k\geq 4$, and for $k=1,2,3$ the statement is obvious.