Inequality on balls/bins with nested logs Let $k = \lceil \frac{3 \ln n}{\ln \ln n}\rceil$. How does one show that 
$$ \left(\frac{e}{k}\right)^k \frac{1}{1-\frac{e}{k}} \le n^{-2} ? $$
This is from p. 44 of Motwani and Raghavan, Randomized Algorithms, where they're talking about ball/bin probabilities. The $\left(\frac{e}{x}\right)^x$ is motivated but the $k$ just comes out of nowhere. Ignoring that for the moment, I don't see the derivation of the inequality; even assuming the the 3 is really an approximation for $e$, and throwing out the $\log\log n$... and the geometric series, I get (letting $k^{*}= e \log n$):
$$
\left(\frac{e}{k^{*}}\right)^{k^{*}}\approx n^{-\log\log n} \le n^{-2}
$$
for $n \ge e^{e^2}$.
But I changed things quite a bit, and this is quite a large constant ($\approx 3^{27}$).
So two questions:


*

*how does one derive the full inequality?

*why that particular $k$?

 A: The inequality does not hold. If you set $n=5.6 \times 10^{6}$ (close to $ e^{e^e}$) with $k=17$, you will find that the left hand side is larger than $3.4 \times 10^{-14}$ and the right hand side is smaller than $3.2 \times 10^{-14}$. To see why the inequality is wrong and why $k=\lceil \frac{4 \log n}{\log \log n} \rceil$ works, read on:
To get a "good" value for $k$, you want that the inequality becomes asymptotically $n\to\infty$ and equality. That is how you derive the particular form. Taking log of your inequality, we get (i switched the sign of the equation because I rather like positive numbers)
$$ L= k (\log k -1) +\log(1- e/k) \geq  2 \log n .$$
The most important term (for $n,k \to \infty$) is $k\log k$. So we would like to have
$$ k\sim \frac{2 \log n}{\log k}.$$
This can be solved iteratively. The first approximation is $k_0 = 2 \log n$. We set this approximation in the right hand side and obtain $k_1 = 2 \log n/ \log \log n$ (up to an irrelevant additive term $\log 2$ in the denominator). This is already almost the estimate, changing the 2 to 3 and the ceiling function are needed to have some space and make the inequality valid (and not only the expressions asymptotically equal). 
Now, let us check the inequality and set $k= c \log n /\log \log n$ ($c$ we will determine in the end). We obtain
$$ L= \frac{c \log n}{\log \log n} ( \log c + \log \log n - \log \log \log n -1) + \log (1- e \log \log n /c \log n).$$ We will use that $(\log c -1) > 0$ (for $c>e$), $(\log \log \log n / \log \log n) \leq 1/e$ (with the maximum attained for $n=e^{e^e}$), and $\log (1- e \log \log n /c \log n)>\log(c-1)-\log c$ (with the minimum at $n=e^e$). Thereby, we can show that $$L \geq c  (1- 1/e) \log n + \log (c-1) - \log c .$$
The lowest value of $c$ for which we can hope that the inequality is always fulfilled is given by $c(1-1/e) =2$, i.e., $c= 2e/(e-1) \approx 3.2$. Assuming that $n>e$ such that $\log n >1$, we can further bound the expression
$$L \geq [c (1-1/e) + \log (c-1) - \log c ] \log n \geq 2 \log n$$
if $c\gtrsim 3.67$.
