# Big O notation while proving the limit of a sum

I'm trying to follow the (rather short) proof given in Makarov's Selected Problems in Real Analysis for the following statement: $\lim_\limits{n\to\infty} \sum\limits_{k=1}^{n}\Big(\frac{k}{n}\Big)^n = \frac{e}{e-1}$. I find a key part of it difficult to understand:

$\sum\limits_{k=n-\sqrt[3]{n}}^{n}\Big(\frac{k}{n}\Big)^n = \sum\limits_{j=0}^{\sqrt[3]{n}} \Big(1-\frac{j}{n}\Big) ^{n-j} = \sum\limits_{j=0}^{\sqrt[3]{n}} e^{-j} \Big(1+O\Big(\frac{j^2}{n}\Big)\Big)$

I don't fully understand the last equality. How can it be proved? And why is the there $j^2$ there? Intuitively, it seems to me that the same equality with $O(\frac{1}{n})$ is correct as well, isn't it?

• Definition of $e$. – Megadeth Sep 28 '15 at 15:16
• The authors chose splitting the sum as $\sum_{k=1}^{n-n^{1/3}-1}\left(\frac kn\right)^n+\sum_{k=n-n^{1/3}}^{n}\left(\frac kn\right)^n$ so that as $n\to \infty$, the first sum approaches $0$ as $e^{-n^{1/3}}$ and the second sum has the form as given in the post. Ido, just curious ... did the author provide any motivation prior to making this somewhat arbitrary choice? Other choices for the split are also suitable for the analysis (e.g., Split at $k=n-n^{2/5}$, $k=n-n^{1/4}$, etc.). – Mark Viola Sep 28 '15 at 23:03
• Not explicitly. Even if there was a reason it is unlikely it would have written. From my experience, the solutions in this book are typically very short and often are more hints than solutions. – CrazyGrapher Sep 29 '15 at 6:38

\begin{align} \left(1-\frac{j}{n}\right)^{n-j}&=e^{(n-j)\log \left(1-\frac jn\right)}\\\\ &=e^{(n-j) \left(-\frac jn+O\left(\frac{j}{n}\right)^2\right)}\\\\ &=e^{-j}e^{\left(\frac {j^2}n+O\left(\frac{j^3}{n^2}\right)\right)}\\\\ &=e^{-j}\left(1+O\left(\frac{j^2}{n}\right)\right) \end{align}
• You're welcome. My pleasure! And please to hear. For the last expression, we have $$e^x=1+O(x)$$where here we have $$x=\frac{j^2}{n}\left(1+O\left(\frac jn\right)\right)$$ – Mark Viola Sep 28 '15 at 17:14
• Thanks again. I actually found an error with my earlier calculation. Now I'm not sure about the move from the second line to the third. For some reason, I got $\frac{j^2}{n} + O\Big(\frac{j^2}{n} \Big)$ when I multiplied $(n-j)$ and $O\Big(\frac{j^2}{n^2} \Big)$. Is this accurate or am I doing something wrong? – CrazyGrapher Sep 28 '15 at 17:44
• $n\times \frac{-j}{n}=-j$ and $-j\times\frac{-j}{n}=+\frac{j^2}{n}$. Also, $(n-j)\times O\left(\frac{j^2}{n^2}\right)=O\left(\frac{j^2}{n}\right)+O\left(\frac{j^3}{n^2}\right)=O\left(\frac{j^2}{n}\right)\times\left(1+O\left(\frac jn\right)\right)$. – Mark Viola Sep 28 '15 at 18:09
• Thanks. I tried something similar, but couldn't prove $1+O\Big(\frac{j}{n}\Big) = O\Big(\frac{j}{n}\Big)$ for $j \le \sqrt[3]{n}$. What am I missing? – CrazyGrapher Sep 28 '15 at 19:53