Deriving a polylog bound

Question

Reading through a paper and it is stated that $k(1-1/d)^{k-1} < 1$ implies that $k < (1+o(1))d \log d$ without proof (assume $k,d > 1$). How is this fact derived? I assume that the $d \log d$ term comes from $\log(1-1/d) < \log \log d$ but apart from that it is not obvious to me.

Answer 1

According to the comments, the problem can be rephrased as follows.

Problem. Let $a \in \mathbb{R}$. Let $d > 1$. If $a < k$ for all $k>1$ satisfying $k(1 - 1/d)^{k-1} < 1$, then $a < (1 + o(1))d\ln d$.

Proof. Consider $d > 4$. Choose $$k = \left(1 + \frac{\ln(\ln d) + \frac{1}{d}}{\ln d - 1}\right)d\ln d.$$

We claim that $k(1 - 1/d)^{k - 1} < 1$. Indeed, we have \begin{align*} \ln k + (k - 1)\ln(1 - 1/d) &= \ln (d\ln d) + \ln\frac{k}{d\ln d} + (k - 1)\ln(1 - 1/d)\\[6pt] &< \ln (d\ln d) + \frac{k}{d\ln d} - 1 + (k - 1)(-1/d)\\[6pt] &= 0 \end{align*} where we use $\ln x \le x - 1$ for all $x > 0$, and $\ln (1 - 1/d) < -1/d$.

Thus, we have $$a < \left(1 + \frac{\ln(\ln d) + \frac{1}{d}}{\ln d - 1}\right)d\ln d = (1 + o(1))d\ln d.$$

We are done.