# Substituting into an upper bound

I'm looking at the following excerpt from The Probabilistic Method by Alon and Spencer:

I'm probably missing something very obvious, but I don't see how $$f(n) < \log_2 n + \log_2 \log_2 n + O(1)$$ follows from $$2^{f(n)} < nf(n)$$. Clearly when you take log of both sides you get $$f(n) < \log_2 n + \log_2f(n)$$. And then it seems they must be using our lower bound, $$f(n) \ge 1 + \left\lfloor \log_2 n \right\rfloor$$ somehow. I don't get how the lower bound is useful though as it doesn't seem we can just substitute it in. E.g., if $$f(n)$$ takes a value much greater than $$1 + \left\lfloor \log_2 n \right\rfloor$$, our upper bound will be artificially low.

We know that $$0 < f(n) - \log_2 n < \log_2 f(n)$$.

Let $$x_n := f(n) - \log_2 n - \log_2 \log_2 n$$.

We can rewrite the first equation as $$0 < \log_2\log_2 n + x_n < \log_2 \left(\log_2 n + \log_2 \log_2 n + x_n\right)$$

The right handside can be rewritten by noting that if $$a \neq 0$$, $$\log(a + b) = \log(a(1 + b/a)) = \log a + \log(1 + b/a)$$:

$$\log_2\log_2 n + x_n < \log_2 \log_2 n +\log_2\left(1 + \frac{\log_2\log_2 n}{\log_2 n} + \frac{x_n}{\log_2 n}\right)$$

As $$n \to \infty$$, $$\frac{\log_2\log_2 n}{\log_2 n} \to 0$$, so effectively for large $$n$$ we have for very small $$\epsilon$$ $$x_n < \log_2\left(1 + \frac{x_n}{\log_2 n}\right) + \epsilon,$$

which can only happen if $$x_n$$ is either very small or negative.

In any case, since $$x_n$$ is bounded for large $$n$$, it follows that there must be a constant $$C$$ such that $$x_n < C$$. This shows that $$f(n) < \log_2 n + \log_2 \log_2 n + O(1)$$.