Why is $\sum_{t=0}^{n-1} \exp \{ -t \Delta^2 \} \geq \frac{1-e^{-1}}{\Delta^2}$ for $n \geq \frac{1}{\Delta^2}$? This is a follow-up question on this question. I was reading a paper about lower bounds for bandit problems (https://arxiv.org/abs/1302.1611). In Theorem 5, they prove a lower bound with an example problem with two arms. In the comments/answers of the previous question on stackexchange, it turned out that the theorem in the paper contains a few errors: the lower bound in Thrm. 5 should be $\frac{1-e^{-1}}{4\Delta}$, is should only hold for $n \geq 1/\Delta^2$, and the sum should start at 0.
I still don't understand the following step in the corrected proof:
$\sum_{t=0}^{n-1} \exp \{ -t \Delta^2 \} \geq \frac{1-e^{-1}}{\Delta^2}$ for $n \geq 1 / \Delta^2$.
I've tried to use:

*

*Jensen's inequality,

*Taylor expansion,

*infinite sums,
all leading to an upper bound in stead of a lower bound.


Let $\delta = \Delta^2$ for short.
The sum equals $\frac{1 - e^{-n \delta}}{1 - e^{- \delta}}$. Since $n \delta \ge 1$, the top is $\ge 1 - e^{-1}$. The bottom is a concave function of $\delta$ and thus below its tangent line at $\delta = 0$, i.e. $1 - e^{-\delta} \le \delta$ for all $\delta$. Put it together and the desired inequality follows.
