28
$\begingroup$

How should I calculate the below limit
$$\lim_{n\rightarrow \infty} \frac{1^n+2^n+3^n+...+n^n}{n^n}$$ I have no idea where to start from.

$\endgroup$
  • 2
    $\begingroup$ If this question does not come out from you, then where did you get this question? $\endgroup$ – Megadeth Oct 12 '15 at 5:37
  • 5
    $\begingroup$ The limit should at least bigger than $1 + e^{-1} + e^{-2} + \cdots = \frac{e}{e-1}$ as for all $n$, the last term is $1$, the second last is $\left(\frac{n-1}{n}\right)^n = (1- \frac 1n)^n$ which tends to $e^{-1}$. So on so forth. $\endgroup$ – user99914 Oct 12 '15 at 6:05
  • 1
    $\begingroup$ From $\frac{x_1+x_2+\cdots+x_n}{n}\geq\sqrt[n]{x_1x_2\cdots x_n}$ we write $$(\frac1n)^n+(\frac2n)^n+\cdots+(\frac1n)^n\geq n\frac{n!}{n^n}\to e$$ $\endgroup$ – Nosrati Oct 12 '15 at 6:29
  • 2
    $\begingroup$ @Maryam $n^n\sim e^nn!$, so $n\dfrac{n!}{n^n}$ does not approach $e$. $\endgroup$ – Quang Hoang Oct 12 '15 at 6:35
  • 3
    $\begingroup$ Have you tried Stolz-Cesaro ? $\endgroup$ – Lucian Oct 12 '15 at 6:49
20
$\begingroup$

First we use an observation by @Stan in the comment. Note that as $(1 +\frac{x}{n})^n$ is increasing in $n$ whenever $|x|<n$,

$$ \left(\frac{k}{n}\right)^n = \left(1 + \frac{k-n}{n}\right)^n \le e^{k-n}, $$

(here we assume that $x:= k-n$ is fixed and varies the remaining two $n$'s. This sequence is increasing and tends to $e^{k-n}$, as $|x| = |k-n| < n$. See here). Then we have

$$\begin{split} \frac{1^n + 2^n + \cdots + n^n}{n^n} &= \sum_{k=1} ^n \left(\frac{k}{n}\right)^n \\ &\le \sum_{k=1}^n e^{k-n} \\ &= 1 + e^{-1} + e^{-2} + \cdots e^{1-n} \\ &\le \frac{1}{1-e^{-1}} = \frac{e}{e-1}. \end{split} $$ This implies

$$\limsup_{n\to \infty} \frac{1^n + 2^n + \cdots + n^n}{n^n} \le \frac{e}{e-1}.$$

On the other hand, fix $k$. Then for all $n >k$, we have

$$\begin{split} \frac{1^n + 2^n + \cdots + n^n}{n^n} &\ge \frac{(n-k)^n + (n-k+1)^n + \cdots + n^n} {n^n}\\ &= \left( 1 - \frac kn\right)^n + \left( 1 - \frac {k-1}n\right)^n + \cdots +1 \end{split}$$

Then for all $\epsilon >0$, there is $N\in \mathbb N$ so that

$$ \left| \left( 1 - \frac {j-1}n\right)^n - e^{-(j-1)} \right| < \epsilon$$

whenever $n \ge N$ and for all $j = 1, 2 , \cdots, k+1$ (Note $k$ is fixed, so this $N$ can be found)

In particular, this implies

$$ \frac{1^n + 2^n + \cdots + n^n}{n^n} \ge e^{-k} + e^{-(k-1)} + \cdots + 1 - (k+1) \epsilon. $$

Thus

$$ \liminf_{n\to \infty} \frac{1^n + 2^n + \cdots + n^n}{n^n} \ge e^{-k} + e^{-(k-1)} + \cdots + 1 - (k+1) \epsilon. $$

Now let $\epsilon \to 0$ and then $k \to \infty$, we have

$$ \liminf_{n\to \infty} \frac{1^n + 2^n + \cdots + n^n}{n^n} \ge \frac{1}{1-e^{-1}} = \frac{e}{e-1}. $$

This implies

$$\lim_{n\to \infty} \frac{1^n + 2^n + \cdots + n^n}{n^n} = \frac{e}{e-1}.$$

$\endgroup$
  • 1
    $\begingroup$ Another proof for $e^{k-n} \geq (k/n)^n = e^{n \ln (k/n)}$: $\Leftarrow k-n \geq n \ln (k/n) \Leftarrow \frac{k}{n}-1 \geq \ln \frac{k}{n}$ $\Leftarrow$ for $x>0$, $x-1 \geq \ln x$ $\Leftarrow$ Let $y(x) = x-1-\ln x$, then the stationary point should satisfy $y'=1-\frac{1}{x}=0$; meanwhile $y''=x^{-2}>0$. Thus $y_{\min} = y(1) = 0$, for all $x>0$, $y(x) \geq 0$. $\endgroup$ – Stan Oct 12 '15 at 8:01
  • 1
    $\begingroup$ Another proof for the upper bound: $$1^n+2^n+\cdots+(n-k-1)^n < \int_1^{n-k} x^n\,dx < (n-k)^{n+1}/(n+1) < (n-k)^n.$$ Thus when we take only the terms from $(n-k)^n$ to $n^n$ in the numerator, the neglected terms are at most $(n-k)^n/n^n$, which tends to $e^{-k}$ as $n\to\infty$. Now we have the limit sandwiched between two explicit functions of $k$; let $k\to\infty$. $\endgroup$ – Greg Martin Oct 12 '15 at 8:10
  • $\begingroup$ Nice proof! +1 :) $\endgroup$ – ZFR Nov 21 '15 at 7:50

Not the answer you're looking for? Browse other questions tagged or ask your own question.