8
$\begingroup$

I'm asked to find $\displaystyle\lim_{n\to \infty}\sum_{k=1}^n \left(\frac{k}{n}\right)^n$.

It seems that the sum converges.

I managed to prove that $\forall n,1<\sum_{k=1}^n \left(\frac{k}{n}\right)^n<e$

But I don't know how to prove convergence, nor find the value of the limit.

$\endgroup$

marked as duplicate by YuiTo Cheng, Cesareo, kingW3, Adrian Keister, José Carlos Santos sequences-and-series Jun 26 at 18:34

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You can turn this into $\displaystyle \lim_{n \to \infty} \left (\frac{1}{n}\right )^n H_n^{-n}$, but I'm not sure if this is easier. $\endgroup$ – UserX Sep 11 '14 at 16:49
  • $\begingroup$ What is $H_n^{-n}$? $\endgroup$ – Idonknow Sep 11 '14 at 17:41
  • $\begingroup$ math.stackexchange.com/questions/1475930/…. $\endgroup$ – StubbornAtom Jan 23 at 14:03
9
$\begingroup$

Let $( b_{k,n} )_{k, n\in\mathbb{Z}_{+}}$ be the double sequence defined by

$$b_{k,n} = \begin{cases} 0,& n \le k\\ \left(1 - \frac{k}{n}\right)^n,& n \ge k\\ \end{cases}$$ We have $$\sum_{k=1}^n \left(\frac{k}{n}\right)^n = \sum_{k=0}^{n-1}\left(1 - \frac{k}{n}\right)^n = 1 + \sum_{k=1}^\infty b_{k,n}$$ This implies

$$\lim_{n\to\infty}\sum_{k=1}^n \left(\frac{k}{n}\right)^n = 1 + \lim_{n\to\infty} \sum_{k=1}^\infty b_{k,n}\tag{*1} $$

If we fix $k$, then for any $n \ge k$, apply AM $\ge$ GM to the list of numbers consisting of $n$ copies of $1 - \frac{k}{n}$ and $1$ copy of $1$, we get

$$\left(1 - \frac{k}{n}\right)^{\frac{n}{n+1}} \le \frac{1}{n+1}\left[n\left(1-\frac{k}{n}\right) + 1\right] = 1 - \frac{k}{n+1} \quad\implies\quad b_{k,n} \le b_{k,n+1} $$

So for each fixed $k$, $b_{k,n}$ as a sequence of $n$ is non-negative and monotonic increasing. Furthermore, we know

$$\lim_{n\to\infty} b_{k,n} = \lim_{n\to\infty} \left(1 - \frac{k}{n}\right)^n = \lim_{n\to\infty} \left(1 - \frac{k}{n}\right)^{\frac{n}{k}k} = \left(\lim_{x\to 0}(1 - x)^{\frac{1}{x}}\right)^k = e^{-k}$$

By monotone convergence theorem for series${}^{\color{blue}{[1]}}$, we can exchange the limit and summation in $(*1)$ and get

$$\lim_{n\to\infty}\sum_{k=1}^n \left(\frac{k}{n}\right)^n = 1 + \sum_{k=1}^\infty \left(\lim_{n\to\infty} b_{k,n}\right) = 1 + \sum_{k=1}^\infty e^{-k} = \frac{e}{e-1}$$

Notes

  • $\color{blue}{[1]}$ for the statement and a proof of monotone convergence theorem for series, see this.
$\endgroup$
  • $\begingroup$ What am I missing here? I thought $\sum_{k=1}^\infty e^{-k} =\frac{1}{1-1/e}= \frac{e}{e-1}$, so shouldn't the result be $1+\frac{e}{e-1}$? $\endgroup$ – Scounged Aug 1 '15 at 21:16
  • $\begingroup$ @Scounged $\sum_{k=\color{red}{a}}^\infty x^k = \frac{x^{\color{red}{a}}}{1-x}$ for $|x| < 1$. $\endgroup$ – achille hui Aug 1 '15 at 21:41
  • $\begingroup$ Oh, I missed that $k=1$, and just assumed it was 0 for some reason. My bad. $\endgroup$ – Scounged Aug 1 '15 at 22:55
2
$\begingroup$

Answer changed

$$ \lim_{n\rightarrow +\infty}\sum_{k=0}^n\left(\frac{k}{n}\right)^n=\lim_{n\rightarrow +\infty}\int_{\Bbb{N}_0}u_nd\nu=\int_{\Bbb{N}_0}e^{-k}d\nu(k)=\sum_{k=0}^{+\infty}e^{-k}=\frac{e}{e-1} $$

using the Monotone Convergence Theorem and as achille hui $$u_n=\begin{cases} 0,& n \le k\\ \left(1 - \frac{k}{n}\right)^n,& n \ge k\\ \end{cases}$$

$\endgroup$
  • $\begingroup$ Can you expand a little bit more ? I edited things I thought were incorrect. $\endgroup$ – Gabriel Romon Sep 11 '14 at 18:22
  • $\begingroup$ @G.T.R I misread the question, sorry. I edited my answer. $\endgroup$ – Krokop Sep 11 '14 at 18:54
1
$\begingroup$

Do you know what $(\frac{n-1}{n})^n$ approaches, and $(\frac{n-2}{n})^n$?

$\endgroup$
  • 4
    $\begingroup$ It should be a comment ! $\endgroup$ – idm Sep 11 '14 at 16:48
  • 1
    $\begingroup$ This hint leads directly to the sum $1+1/e+1/e^2+...$ $\endgroup$ – Empy2 Sep 11 '14 at 16:52
  • 1
    $\begingroup$ Well, not directly (there is an exchange of limit and sum which needs some justification) but yes, it does lead to it. $\endgroup$ – Did Sep 11 '14 at 17:15
  • $\begingroup$ It's not sufficient a hint. How do you prove that $\sum_{k=1}^{n-1} \left(\left(1-\frac{k}{n}\right)^n-\frac{1}{e^k}\right) \to 0$ ? $\endgroup$ – Gabriel Romon Sep 11 '14 at 17:48
  • $\begingroup$ @G.T.R Monotonicity. $\endgroup$ – Daniel Fischer Sep 11 '14 at 17:56
1
$\begingroup$

It's easier to write the sum as $$\sum_{k = 0}^{n - 1} \bigg({n - k \over n}\bigg)^n = \sum_{k = 0}^{n - 1} \bigg(1 - {k \over n}\bigg)^n \tag 1$$ Note that $\ln (1 - {k \over n}) = -k/n - {1 \over 2}(k/n)^2 - ...$, so we have $$\ln \bigg(1 - {k \over n}\bigg) < -{k \over n}$$ Exponentiating both sides gives $$1 - {k \over n} < e^{-{k \over n}}$$ So taking $n$th powers we get $$\bigg(1 - {k \over n}\bigg)^n < e^{-k} \tag 2$$ Note also that since $\lim_{t \rightarrow 0} (1 + t)^{1 \over t} = e$, we also have $$\lim_{n \rightarrow \infty} \bigg(1 - {k \over n}\bigg)^n = \bigg(\lim_{n \rightarrow \infty} \bigg(1 - {k \over n}\bigg)^{n \over k}\bigg)^n$$ $$= e^{-k} \tag 3$$ So the limit of $(1)$ as $n \rightarrow \infty$ can be evaluated as follows. Fix some $N$. Then by $(3)$, the sum of the $k = 0$ through $k = N$ terms of the sum $(1)$ goes to $\sum_{k = 0}^N e^{-k}$ as $n$ goes to infinity, while by $(2)$ for any $n > N$ the sum of the remaining terms is between $0$ and $\sum_{k = N +1}^{\infty} e^{-k} = {\displaystyle {e^{-N - 1} \over 1 - {1 \over e}}}$. Hence we have $$ \limsup_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n \leq \limsup_{n \rightarrow \infty} \sum_{k = 0}^N \bigg({n - k \over n}\bigg)^n + {e^{-N - 1} \over 1 - {1 \over e}}$$ $$ = \sum_{k = 0}^N e^{-k} + {e^{-N - 1} \over 1 - {1 \over e}}$$ $$\liminf_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n \geq \liminf_{n \rightarrow \infty} \sum_{k = 0}^N \bigg({n - k \over n}\bigg)^n$$ $$\geq \sum_{k = 0}^N e^{-k} $$ Letting $N$ go to $\infty$ we get $$\lim_{n \rightarrow \infty} \sum_{k = 0}^n \bigg({n - k \over n}\bigg)^n = \sum_{k = 0}^\infty e^{-k} $$ $$={1 \over 1 - {1 \over e}}$$

$\endgroup$
  • $\begingroup$ I think your proof is flawed. First you fix some $N$ that does not depend on $N$, and then you set $N=\lfloor n/2 \rfloor$. $\endgroup$ – Gabriel Romon Sep 12 '14 at 13:51
  • $\begingroup$ I botched the end there, this should correct it. $\endgroup$ – Zarrax Sep 12 '14 at 23:56

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