In the book Randomized Algorithms from Motwani and Raghavan, it is stated in page 44 that
$$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$
This inequality is used to prove the theorem "With probability at least $1 - \frac{1}{n}$, no bin has more than $k^\ast = (e \ln n)/ \ln \ln n$ balls in it".
This problem arises from a balls and bins game. The proof starts like this.
Consider first the case $m = n$, and let $X_j(k)$ denote the event that bin $j$ has $k$ or more balls in it. We concentrate on analyzing $X_1(k)$. The probability that bin 1 receives exactly $i$ balls is $$\binom{n}{i} \left( \frac{1}{n} \right)^i \left( 1 - \frac{1}{n} \right)^{n-i} \leq \binom{n}{i} \left( \frac{1}{n} \right)^i \leq \left(\frac{ne}{i} \right)^i \left( \frac{1}{n} \right)^i = \left( \frac{e}{i} \right)^i.$$ The second inequality results from an upper bound for binomial coefficients (for reference). Thus $$\mathbb{P}[X_1(k)] \leq \sum_{i = k}^n \left( \frac{e}{i} \right)^i \leq \left( \frac{e}{k} \right)^k \left( 1 + \frac{e}{k} + \left( \frac{e}{k} \right)^2 + \cdots \right).$$ Let $k^\ast = \lceil(e \ln n)/ \ln \ln n \rceil$. Then, $$\mathbb{P}[X_1(k^\ast)] \leq \left( \frac{e}{k^\ast} \right)^{k^\ast} \frac{1}{1-e/k^\ast} \leq n^{-2}.$$
However, I don't understand how the authors can go so fast on the second inequality.
I tried to developp $k^\ast$ and simplify it a bit, I tried to use that $x = \exp(\ln x)$, I tried to reproduce the proof of theorem 7.1.1 here but I just could not arrive to the conclusion.
Could someone explain this to me?
Edit: Actually, this inequality might be wrong. I plotted it in mathematica, and here is the result:
If the inequality was correct, the plot should be below 0, and this is clearly not the case. Even for greater $n$, the function seems to be increasing. I was to lazy too compute the derivative and check it out formally. (The discontinuity may come from the ceiling approximation, I did not check it out. I tried with $k = \frac{e \ln n}{\ln \ln n}$ and the plot was continous).
What do you think? Am I wrong, or is it possible that there is an error in the book?