Desigualdades logarítmicas y expansiones asintóticas

Question

Estoy tratando el método probabilístico y cómo se aplica a las sumas distintas. En los apuntes que estoy utilizando me encuentro con la siguiente desigualdad:

$2^k\le nk$ que las notas simplifican en esta forma:

$k\le \log_2n +\log_2\log_2n + O(1)$ Y no tengo ni idea de cómo se llega a esto.

Claramente tomando una $\log_2$ en ambos lados da $\log_2 2^k\le \log_2 nk \implies k\le \log_2 n +\log_2 k$

Pero, ¿cómo pasamos de $\log_2k$ a $\log_2\log_2n + O(1)$ ?

Seguro que se me escapa algo obvio pero cualquier ayuda se agradecería.

Answer 1

Toma el $\log_2$ de la desigualdad inicial: $$ k \le \log _2 n + \log _2 k. $$ Tomando la $\log_2$ vuelve a dar $$ \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). $$ Sustituyendo esto en la primera desigualdad se obtiene $$ k \le \log _2 n + \log _2 \log _2 n + \log _2 \left( {1 + \frac{{\log _2 k}}{{\log _2 n}}} \right). $$ Así, queda por demostrar que el último término es $\mathcal{O}(1)$ . Pero $$ 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 $$ siempre que $k\geq 4$ y para $k=1,2,3$ la afirmación es obvia.