$\ln(\ln n) / \ln n$ inequality I am reading a book, Randomized Algorithms by Motwani.
In the Section 3.1 Occupancy problems, there is one step in the analysis that really puzzles me:
Let $k=\lceil (e \ln n) / (\ln\ln n) \rceil$,
$$(e/k)^k \; 1/(1-e/k) \le n^{-2}.$$
The book does not mention a single word about the above inequality.
Could anyone point out any clue for me? Thanks.
I try to simplify the inequality and get the following, but I have no idea about how to proceed.
$$\begin{align}
\ln \frac{(e/k)^k}{1-e/k} &= k - k \ln k - \ln(1-e/k)\\
&\le k - k\, \ln \frac{e \ln n}{\ln\ln n} - \ln(1-e/k)\\
&= - k \,\ln \frac{\ln n}{\ln\ln n} - \ln(1-e/k)\\
&...\\
&\le -\ln n^2
\end{align}$$
 A: Take logs. Use $\ln(1-z) \approx -z$.
A: $$\begin{align}
\ln \frac{(e/k)^k}{1-e/k} &= k - k \ln k - \ln(1-e/k)\\
&\le k - k\, \ln \frac{e \ln n}{\ln\ln n} - \ln(1-e/k)\\
&= - k \,\ln \frac{\ln n}{\ln\ln n} - \ln(1-e/k)\\
&\le - \frac{e \ln n}{\ln\ln n} \,\ln \frac{\ln n}{\ln\ln n} - \ln \frac{\ln n}{\ln\ln n} - \ln(1-e/k)\\
&\le - \frac{e \ln n}{\ln\ln n} \,\ln \frac{\ln n}{\ln\ln n} + 1\\
&...\\
&\le -\ln n^2
\end{align}$$
First, we prove the second to last step. $- \ln \frac{\ln n}{\ln\ln n} - \ln(1-e/k) \le - \ln \frac{\ln n}{\ln\ln n} - \ln(1-\frac{\ln\ln n}{\ln n}) = \ln \frac{\ln\ln n}{\ln n-\ln\ln n} \le 1$, because $\frac{\ln\ln n}{\ln n-\ln\ln n} \le 1$ (Intuitively I think this is right, tho I didn't prove this rigorously. One fact is that $\lim \frac{\ln\ln n}{\ln n} \to 1$).
Now in order to reach the last step, we need to prove $\frac{e \ln n}{\ln\ln n} \,\ln \frac{\ln n}{\ln\ln n} - 1\ge 2\ln n$.
This is mainly done by discussing the size of $k$. $k$ is obviously monotone increasing as $n$.
When $n\ge e^2$, we have $\ln\ln e\ge 1, \ln n\ge 2e, \frac{\ln n}{\ln\ln n}\ge 2e, k\ge e^2$.
To prove
$$\frac{e \ln n}{\ln\ln n} \,\ln \frac{\ln n}{\ln\ln n} -1 = e \ln n \,\ln (\frac{\ln n}{\ln\ln n}^{\frac{1}{\ln\ln n} }) - 1\ge 2\ln n,$$
We only need to prove, which obviously holds.
$$\ln (\frac{\ln n}{\ln\ln n}^{\frac{1}{\ln\ln n} }) \ge \ln (2e) \ge 1.$$
Now we discuss the case when $n<e^2$. All of them are trivial as $k\ge n$. We prove by enumeration.
>>> import numpy as np
>>> f = lambda n: np.e * np.log(n) / np.log(np.log(n))
>>> f(1)
__main__:1: RuntimeWarning: divide by zero encountered in log
-0.0
>>> f(2)
-5.1407993540132235
>>> f(3)
31.753395017048458
>>> f(4)
11.536875436697946
>>> f(5)
9.193199773814012
>>> f(6)
8.35137728786035
>>> f(7)
7.945463931375426
>>> f(8)
7.720957567366346
>>> np.e**2
7.3890560989306495

