How can I prove that $\lim_{n\to\infty}\frac{1}{n}\sum_{k=1}^{n}\exp(-\frac{(k-1)k}{2n})=0$?

Question

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.

Answer 1

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) . $$

Answer 2

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$

Answer 3

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 $.