# Evaluate the following limit

Given positive integer $k$, evaluate

$$\lim_{n\to\infty}n\cdot\left(\sum_{i = 1}^n\left(\dfrac{i}{n}\right)^{k}\right)^{-1}$$

-

\begin{align*} \lim_{n\to\infty}n\cdot\left(\sum_{i = 1}^n\left(\dfrac{i}{n}\right)^{k}\right)^{-1} &= \lim_{n\to\infty}\left(\frac1n \sum_{i = 1}^n\left(\dfrac{i}{n}\right)^{k}\right)^{-1}\\ \\ &=\left(\lim_{n\to\infty}\frac1n \sum_{i = 1}^n\left(\dfrac{i}{n}\right)^{k}\right)^{-1}\\ &= \left(\int_0^1 x^k dx\right)^{-1} \\ &= \left(\frac1{k+1}\right)^{-1} \\ &= k+1\\ \end{align*}

-
Uh I see! That's clever, recognizing the limit of sum as an integral. Thank you! – darksky Aug 27 '12 at 7:11

The tricky part here is

$$\sum_{i=0}^n i^k = \frac{n^{k+1}}{k+1} + o(n^k)$$

Once you've got that

$$\lim_{n\to\infty} n \left( \sum_{i=0}^n \left(\frac{i}{n}\right)^k \right)^{-1} = \lim_{n\to\infty} n . n^{k} \left( \frac{n^{k+1}}{k+1} + \ldots \right)^{-1} = k+1$$

NOTE:

To show the top result I used

$$S_n = S_{n-1} + n^k$$ and assumed that $S_n = T_n + \alpha n^{k+1}$. In that case

$$T_n = T_{n-1} + \alpha n^{k+1} - \alpha (n-1)^{k+1} + n^k$$

And we get a reduction in the order iff the first two terms ($n^{k+1}$ and $n^k$) cancel, which will only occur if $\alpha = 1/(k+1)$.

However I'm sure there's a more elegant way to do that.

-