How can I prove that $\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp(-\frac{(k-1)k}{2n})=0$? How can I prove that $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)k}{2n}\right)=0?$$ I'm really trying to avoid big-O notation and complicated asymptotic-behaviour arguments.
It seems that each of the terms converges to $1$ as $n$ gets large. There are $n$ such terms, so if we divide the sum by $n$, it looks like the entire limit behaves like $n/n\to1\neq0$? My intuition is clearly wrong.
 A: If the $n$ is the denominator in the exponential was $n^2$, then the limit could be computed via Riemann sums. 
If the term $k(k-1)$ was $k$, we could also use Riemann sums. 
Fix an $R>0$; for $n\geqslant R$, 
$$
0\leqslant \frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)k}{2n}\right)=
\frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)kn}{2n^2}\right)\leqslant
\frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)kR}{2n^2}\right).
$$
Using Riemann sums, we derive that for all $R$, 
$$
0\leqslant \limsup_{n\to +\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)k}{2n}\right)\leqslant\int_0^1\exp\left(-Rt^2/2\right)dt.
$$
Now, we control the last integral in the following way: we use the fact that $\exp\left(-Rt^2/2\right)$ is small than one and that $\exp\left(-Rt^2/2\right)\leqslant \exp\left(-R\delta^2/2\right)$ for $t\geqslant \delta$ to get 
$$ 
\int_0^1\exp\left(-Rt^2/2\right)dt\leqslant\delta+ \exp\left(-R\delta^2/2\right) .
$$
A: I will prove the following, stronger, result:
Theorem. We have
$$\lim_{n\to\infty}\sum_{k=1}^{\infty} \frac{1}{2n +(k-1)k}=0.$$
Proof. We have by this result that for all $n\in\mathbb N$,
\begin{split}
\sum_{k=1}^{\infty} \frac{1}{2n +(k-1)k}&=\frac{\pi  \tan \left(\frac{1}{2} \pi  \sqrt{1-8n}\right)}{\sqrt{1-8n}} \\
&=\frac{\pi\tanh(\frac12\pi\sqrt{8n-1})}{\sqrt{8n-1}}\\
&\le\frac{2\pi}{\sqrt{8n-1}}\xrightarrow{n\to\infty}0,\end{split}
where I used $\tanh(x)\le2$ for $x\geq 0$. $\square$
Corollary. We have $$\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp\left(-\frac{(k-1)k}{2n}\right)=0.$$
Proof. Using the bound $\exp(x)\geq 1+x$, we get $$\frac{1}{n}\sum_{k=1}^{n}\frac{1}{\exp\left(\frac{(k-1)k}{2n}\right)}\le\frac1n\sum_{k=1}^n \frac{1}{1+\frac{(k-1)k}{2n}}=\sum_{k=1}^n \frac{2}{2n+(k-1)k}<2\sum_{k=1}^{\infty} \frac{1}{2n +(k-1)k}.$$
But by the Theorem, the last sum converges to $0$ as $n\to\infty$ so we are done. $\square$
A: Here's a completely elementary
proof of convergence.
I would split the sum
into two parts:
first, a small part where the terms
are large;
second,
a large part
where the terms are small.
Choose
$0 < a < 1$
and let
$s
=\sum_{k=1}^{n}\exp\left(-\frac{(k-1)k}{2n}\right)
=s_1+s_2
$
where
$s_1
=\sum_{k\le n^a}\exp\left(-\frac{(k-1)k}{2n}\right)
$
and
$s_2
=\sum_{k\gt n^a}\exp\left(-\frac{(k-1)k}{2n}\right)
$.
Since
$\frac{(k-1)k}{2n}
\gt 0$,
$s_1 < n^a
$.
If $k-1 \ge n^a$,
then
$\frac{(k-1)k}{2n}
\ge \frac1{2}n^{2a-1}
$
so
$s_2
\le (n-n^a)e^{-\frac1{2}n^{2a-1}}
\lt ne^{-\frac1{2}n^{2a-1}}
$.
Choose
$2a > 1$,
or $a = \frac12(1+c)$
where
$1 > c > 0$.
Then
$s_2
\lt ne^{-n^c/2}
$.
A value which works is
$a = \frac23$
so that
$c = 2a-1 = \frac13
$.
Then
$s \lt n^a+ne^{-n^c/2}
$
so
$\dfrac{s}{n}
 \lt n^{a-1}+e^{-n^c/2}
 = n^{(c-1)/2}+e^{-n^c/2}
 \to 0
$.
