Derive asymptotic behaviour of $k:=k(n)$ from $2^k/kLet $k:=k(n)$ be a function that satisfies
$$ \frac{2^k}{k}<n.$$
I'm trying to show that
$$ k<\log_{2}n+\log_{2}\log_{2}n + \mathcal{O}(1).$$
If I take $\log$ on both sides I get that
$$ k-\log_2 k < \log_2 n,$$
therefore, it suffices to show that $\log_2 k = \log_2\log_2 n + \mathcal{O}(1).$ To that end, I've tried to take the log one more time (but I'm not sure where it goes).
$$\log_{2}\left(k\left(1-\frac{\log_{2} k}{k}\right)\right)\approx\log_{2}k-\frac{\log_{2}k}{k}=\log_{2}k\left(1-\frac{1}{k}\right)\leq \log_2 k\cdot e^{-k}.$$
Where the first approximation relies on $\ln(1+x)=x+\mathcal{O}(x^{-2})$, for $x$ small enough.
 A: For large enough $k$, as $k$ increases, $\log_2\left(k-\log_2k\right)$ tends towards $\log_2k$ from below. So, there is some constant $C>0$ so that $\log_2k <\log_2\left(k-\log_2k\right) + C$. This just needs to be greater than the maximum distance between $\log_2\left(k-\log_2k\right)$ and $\log_2k$ (which is finite, since one tends to the other asymptotically).
So, since $k - \log_2k < \log_2n$, taking logs of both sides gives $\log_2\left(k-\log_2k\right) < \log_2\log_2n$, and combining with the earlier inequality gives $\log_2k < \log_2\log_2n + C$.
Putting all the inequalities together, we have $k < \log_2k +\log_2n < \log_2n + \log_2\log_2n + C$, as required.
A: Combining my thoughts with Fred's answer.
Note that
$$
\ln\left(x-\ln\left(x\right)\right)=\ln\left(x\left(1-\frac{\ln x}{x}\right)\right)=\ln x-\frac{\ln x}{x}+\mathcal{O}\left(\frac{\ln^2 x}{x^2}\right)=\ln x\left(1-\frac{1}{x}+\mathcal{O}\left(\frac{\ln x}{x^2}\right)\right)=\ln x\left(1-o\left(1\right)\right).
$$
Similarly, one can derive that
$$
\log_{2}\left(k-\log_{2}\left(k\right)\right)=\log_{2}\left(k\right)\cdot\left(1-o\left(1\right)\right).
$$
Therefore, taking $\log$ on both sides of $k-\log_2 k < \log_2 n$ and substituting the above yields
\begin{align*}
\log_{2}\left(k\right)\cdot\left(1-o\left(1\right)\right)<\log_2 \log_2 n &\implies \log_2 k <(1+o(1))\log_2\log_2 n\\
&\implies \log_2 k< \log_2\log_2 n+\mathcal{O}(1).
\end{align*}
The results follow.
