# Calculat sums of the form $\lim_{n\rightarrow\infty}\sum_{i=0}^{n}\left(\frac{i}{n}\right)^{f(n)}$

Problem: calculate the sums of the form: $$\lim_{n\rightarrow\infty}\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{f(n)}$$

Inspiration: one problem lets us prove that $\sum_{i=1}^{n}\left(\dfrac{2i-1}{2n}\right)^{n}<\dfrac{\sqrt{e}}{e-1}$. After using numeric tools I found that it seems to converge to the bound.

I tried to reduce it into a form of finite sums of sum integral, that is, write $nr^n$ in a form independent of $n$. But it seems impossible.

It is worth noting that $\sum_{i=1}^{n}\left(\dfrac{2i-1}{2n}\right)^{n}=\sum_{i=0}^{2n}\left(\dfrac{i}{2n}\right)^{n}-\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{n}$. So it inspired me to calculate $$\lim_{n\rightarrow\infty}\sum_{i=0}^{n}\left(\dfrac{i}{n}\right)^{kn}$$ or more generally the form in the title.

• For your last sum we should have something like $\lim_{n\to \infty}\sum_{i=1}^n\left(\frac{i}{n}\right)^{nk} = \lim_{n\to \infty}\sum_{i=0}^{n-1}\left(1 - \frac{i}{n}\right)^{nk} = \lim_{n\to\infty}\sum_{i=0}^{n-1}e^{-ki} = \frac{1}{1-e^{-k}}$ giving $\frac{\sqrt{e}}{e-1}$ for the problem you want to solve. I did skip a lot of details in the derivation though so it might be some work to rigorously establishing this. – Winther Jul 31 '15 at 5:21

There is most likely no general algorithm for evaluating expression on the form $\lim\limits_{n\to\infty}\sum_{i=1}^n \left(\frac{i}{n}\right)^{f(n)}$ for a completely general function $f(n)$ - it's simply to broad of a question. The best general answer you could hope to get is a way to determine if the sum converges or not based upon the asymptotic properties of $f(n)$. That being said we can solve in closed form for the example you presented and I have added a proof of this below.

We have

$$I_n = \sum_{i=1}^n\left(\frac{i}{n}\right)^{nk} = \sum_{i=0}^{n-1}\left(1-\frac{i}{n}\right)^{kn}$$

where I have made the substitution $i\to n-i$ to get the last sum. Since $\lim\limits_{n\to\infty}\left(1-\frac{x}{n}\right)^{kx} = e^{-kx}$ it seems natural to study the function $$g(x) = e^{-kx} - \left(1 - \frac{x}{n}\right)^{kn}.$$

This function is positive on $[0,n]$ and has a maximum for $e^{-kx} = \left(1 - \frac{x}{n}\right)^{kn-1}$. The maximum value satisfies $g(x) = \frac{xe^{-kx}}{n}$ and from this it follows that

$$0 \leq \sum_{i=0}^{n-1}e^{-ki} - I_n = \sum_{i=0}^{n-1}g(i) < \frac{1}{n}\sum_{i=0}^{n-1} ie^{-ki} < \frac{1}{n}\sum_{i=0}^{\infty} ie^{-ki}$$

Since $\sum_{i=0}^{\infty} ie^{-ki} < \infty$ for $k>0$ we can conclude that

$$\lim_{n\to\infty}I_n = \sum_{i=0}^{\infty}e^{-ik} = \frac{1}{1-e^{-k}}$$

Using this we get, using the formula you derived, that your first sum satisfies

$$\lim_{n\to\infty}\sum_{i=1}^n \left(\frac{2i-1}{2n}\right)^n = \frac{1}{1-e^{-1/2}} - \frac{1}{1-e^{-1}} = \frac{\sqrt{e}}{e-1}$$

It turns out this problem has been solved before on this site. See this related question for alternative proofs.