# Prove $\lim_{n\to\infty}(1+1/n)^n=e$

I would like to show that $\lim_{n\to\infty}(1+1/n)^n=e$, using the binomial theorem and the power series expansion of $e$. So to be clear: I do not want to use that $e^x:=\lim_{n\to\infty}(1+x/n)^n$, because that's not how I've learned the definition of $e^x$.

Basically I would like to show the following: $$\lim_{n\to\infty}\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}\left(\frac{1}{n}\right)^k=\sum_{k=0}^\infty\frac{1}{k!}$$ I'm guessing this should be possible. Maybe some rewriting could work: $$\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}\left(\frac{1}{n}\right)^k=\sum_{k=0}^n\frac{1}{k!}\cdot\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k$$

EDIT (I was shown a mistake in the comments)

So I have to show the following: $$\lim_{n\to\infty}\sum_{k=0}^n\frac{1}{k!}\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k=\lim_{n\to\infty}\sum_{k=0}^n\frac{1}{k!}.$$

This seems doable, given that I see the term \begin{align}\frac{1}{k!}\end{align} at both sides. So what can I do with \begin{align}\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k\end{align}?

• I don't know how you arrive at that last expression, but I'm not sure if that's correct and I don't think the limit is equal to $1$. – vrugtehagel Apr 9 '17 at 18:55
• For a more direct approach, which is not the one you suggest, note that, for every $x\geqslant0$, $$x-\tfrac12x^2\leqslant\log(1+x)\leqslant x$$ deduce that, for every $n$, $$e\cdot e^{-1/(2n)}\leqslant\left(1+\frac1n\right)^n\leqslant e$$ and conclude. – Did Apr 9 '17 at 18:56
• Oops...., $$\sum_{k=0}^n\frac{1}{k!}\cdot\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k\ne\lim_{n\to\infty}\sum_{k=0}^n\frac{1}{k!}\cdot\sum_{k=0}^n\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k$$ So you need to prove this, $$\lim_{n\to\infty}\sum_{k=0}^n\frac{1}{k!}\cdot\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k=\lim_{n\to\infty}\sum_{k=0}^n\frac{1}{k!}$$ not this, $$\lim_{n\to\infty}\sum_{k=0}^n\frac{n!}{(n-k)!}\cdot\left(\frac{1}{n}\right)^k=1.$$ – Sahil Kumar Apr 9 '17 at 19:04
• $$\sum_{k=0}^n \frac{n!}{(n-k)!}\cdot \frac{1}{n^k}= 1 + 1 + \sum_{k=2}^n \frac{n!}{(n-k)!}\cdot \frac{1}{n^k} >2.$$ How can its limit be $1$? – ntt Apr 9 '17 at 19:06

Notice that, if $k \geq 1$ then

\begin{align*} \frac{n!}{(n-k)!} \cdot \frac{1}{n^k} &= \frac{n(n-1)\cdots(n-k+1)}{n^k} \\ &= \left(1 - \frac{0}{n}\right)\left(1 - \frac{1}{n}\right)\cdots \left(1 - \frac{k-1}{n}\right) \tag{1} \end{align*}

and thus the LHS converges to $1$ as $n \to \infty$. Then, loosely speaking, the result follows from

$$\lim_{n\to\infty} \sum_{k=0}^{n} \frac{1}{k!} \cdot \frac{n!}{(n-k)! n^k} = \sum_{k=0}^{n}\frac{1}{k!} \left( \lim_{n\to\infty} \frac{n!}{(n-k)! n^k} \right) = \sum_{k=0}^{n} \frac{1}{k!} = e. \tag{2}$$

Of course, interchaning limit and infinite summation is a huge leap of faith (and often yields a simply wrong answer), so it should be accompanied by a rigorous justification.

Assuming that you have not been exposed to real analysis, let me give an elementary solution. (But I am not claiming that this is either the most intuitive nor the easiest-to-swallow one.)

We begin by proving the following lemma:

Lemma. If $a_1, \cdots, a_n \in [0, 1]$, then $$(1 - a_1)\cdots(1-a_n) \geq 1 - (a_1 + \cdots + a_n). \tag{*}$$

This is easily proved by invoking mathematical induction. Indeed, the claim is trivial if $n = 1$. Next, assume that that $\text{(*)}$ is true for $n$. If $s_{n+1} := a_1 + \cdots + a_{n+1} > 1$ then

$$(1 - a_1)\cdots(1-a_{n+1}) \geq 0 > 1 - s_{n+1}$$

and the claim is trivial. So we assume that $s_{n+1} \leq 1$. Then $s_n := a_1 + \cdots + a_n \leq 1$ as well and by the induction hypothesis,

\begin{align*} (1 - a_1)\cdots(1-a_{n+1}) & \geq (1 - s_n)(1 - a_{n+1}) \\ &= 1 - (s_n + a_n) + s_n a_n \\ &\geq 1 - s_{n+1}. \end{align*}

Therefore $\text{(*)}$ follows by mathematical induction. ////

Now returning to our problem, applying the lemma to $\text{(1)}$ gives

$$1 \geq \frac{n!}{(n-k)!} \cdot \frac{1}{n^k} \geq 1 - \sum_{j=0}^{k-1} \frac{j}{n} = 1 - \frac{k(k-1)}{2n}.$$

This inequality is also true when $k = 0$. Summing this over $k = 0, \cdots, n$, we have

$$\sum_{k=0}^{n} \frac{1}{k!} - \frac{1}{2n}\sum_{k=2}^{n} \frac{1}{(k-2)!} \leq \left(1 + \frac{1}{n}\right)^n \leq \sum_{k=0}^{n} \frac{1}{k!}.$$

Taking $n \to \infty$ gives the desired proof.

• Oh wow, thank you for your response. After quickly reading through it, it seems to be what should be working for me. I'll read through it more rigorously tomorrow, because I'm off to bed! I'll let you know if things aren't clear. – Sha Vuklia Apr 9 '17 at 19:33
• +1 for mentioning the fact that "any huge leap of faith must be justified rigorously (at least in math)". BTW that leap of faith is a simple consequence of the powerful Monotone Convergence Theorem (en.wikipedia.org/wiki/Monotone_convergence_theorem). – Paramanand Singh Apr 10 '17 at 9:40
• @ParamanandSingh, I definitely agree. The whole proof can be done in a single line if we adopt the monotonicity business:\begin{align*} \lim_{m\to\infty} \sum_{k=0}^{m} \frac{1}{k!} &= \sup_{m \geq 0}\sup_{n \geq 0} \sum_{k=0}^{m} \binom{n}{k}\frac{1}{n^k} \mathbf{1}_{\{k \leq n\}} \\ &= \sup_{n \geq 0}\sup_{m \geq 0} \sum_{k=0}^{m} \binom{n}{k}\frac{1}{n^k} \mathbf{1}_{\{k \leq n\}} = \lim_{n\to\infty}\left(1 + \frac{1}{n}\right)^n.\end{align*} Or even Weierstrass M-test or dominated convergence can be utilized. – Sangchul Lee Apr 10 '17 at 14:52