6
$\begingroup$

$e=2.718\ldots$ is often defined to be $$\lim_{n\to\infty} (1+1/n)^n$$ (from continuously compounded interest) and $$\lim_{n\to\infty}\sum_{k=0}^n \frac{1}{k!}$$ (from Taylor series). My question is, what are the respective rates of convergence for each of these? For example, is the error from $e$ in $O(\frac{1}{n})$? Or is the number of digits of accuracy in $O(n)$? If it's not too involved, a basic overview of a proof would also be appreciated.

And just for bonus points, since I'm curious, what is the state-of-the-art algorithm for calculating digits of $e$?

$\endgroup$
1
  • 1
    $\begingroup$ This is a cool question actually. I thought about this before where x is some irrational number. Of course you can “cheat” with the convergence algorithm, by making a single iteration of a new algorithm simply be two iterations if the previous algorithm. I remember doing some research online and finding some amazingly fast algorithms for computing pi. Like clash fast. $\endgroup$ – Spencer Kraisler Oct 10 '19 at 5:50
5
$\begingroup$

In the first case, \begin{align*} \left(1 + \frac{1}{n}\right)^n &= \exp \left[n \log \left(1 + \frac{1}{n}\right)\right] = \exp \left[1 - \frac{1}{2n} + O\left(n^{-2}\right)\right] = e - \frac{e}{2n} + O(n^{-2}) \end{align*} as $n\to\infty$. In the second case, \begin{align*} \sum_{k \leq n} \frac{1}{k!} - e = \sum_{k > n} \frac{1}{k!} &= \sum_{k > 0} \frac{1}{(k + n)!} \leq \sum_{k > 0} \frac{1}{n^k\, n!} = \frac{1}{n!(n-1)} = O\left(\frac{1}{n!}\right) \end{align*}

$\endgroup$
2
  • 1
    $\begingroup$ So as a corollary, it's safe to say that, the limit expression has an error of $O(\frac{1}{n})$, and the number of digits of accuracy that the series gives you is $O(n \log n)$ (due to Stirling's approximation), yeah? $\endgroup$ – chausies Oct 10 '19 at 6:24
  • $\begingroup$ @chausies: Sure. $\endgroup$ – anomaly Oct 10 '19 at 6:44
5
$\begingroup$

The Laurent series expansion of $\left(1+\frac{1}{n}\right)^n$ about the point $n = \infty$ gives you an idea of the error

$$ \left(1+\frac{1}{n}\right)^n = e - \frac{e}{2n} + \frac{11e}{24n^2} - \frac{7e}{16n^3} + O\left( \frac{1}{n^4} \right) $$

On the other hand

$$ \sum_{r = 1}^n \frac{1}{r!} = e + O\left(\frac{1}{n!}\right) $$

Hence clearly the summation converges faster than the limit.

Example: For $n = 10$, the limit is $2.59374...,$ whereas the sum is $2.71828...$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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