# 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{eqnarray*} \lim_{n\to\infty}n\cdot\left(\sum_{i = 1}^n\left(\dfrac{i}{n}\right)^{k}\right)^{-1} &=& \lim_{n\to\infty} { 1 \over { \sum_{i = 1}^n \left(\dfrac{i}{n}\right)^{k} \over n}} \\ &=& { 1 \over \lim\limits_{n\to\infty}\sum_{i = 1}^n {1 \over n}\left(\dfrac{i}{n}\right)^{k} } \\ &=& {1 \over \int_0^1 x^k dx} \\ &=& k+1\\ \end{eqnarray*}$$

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

-