Proof of $\lim_{n \to \infty}(1+\frac{1}{n})^n=e$

Question

I have this messy proof of $\lim_{n \to \infty}(1+\frac{1}{n})^n=e$ in my notebook. I can't find it anywhere else, but I need it since the professor accepts only this version at the exam. At the time I am only stuck with the first part, so I will write the proof only to that point. Also, there is a few steps with missing reasoning between them.

Proof.

We are given two sequences:

$$x_n=1+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+\dots+\frac{1}{n!}$$ $$y_n=\left(1+\frac{1}{n}\right)^n$$

If $x_n$ converges, then $\lim_{n \to \infty}x_n=e$. (This is given.)

Let's prove that $x_n$ converges.

To prove that, the Monotone Convergence Theorem will be used.

Since $x_{n+1}>x_{n}$ the sequence is increasing. (I skipped the unnecessary reasoning for this.)

Now let's prove that it is bounded from above.

$$n!=1\cdot 2\cdot 3\cdots n>2^{n-1}\tag{1.1}$$ $$\frac{1}{n!}\leq \frac{1}{2^{n-1}}\tag{1.2}$$

$$\underbrace{2}_{\text{?}}\leq x_n\leq 1+1+\frac{1}{2}+\frac{1}{2^2}+\dots+\frac{1}{2^{n-1}}\tag{1.3}$$

$$1+q+q^2+\dots+q^{n-1}=\underbrace{\overbrace{\frac{1-q^n}{1-q}}^{?}=\frac{q^n-1}{q-1}}_{\text{?}}\tag{1.4}$$

$$q=\frac{1}{2}$$

$$\underbrace{1}_{\text{?}}+\frac{1-\frac{1}{q^n}}{1-\frac{1}{q}}=1+2\left(1-\frac{1}{2^n}\right)<1+2=3\tag{1.5}$$

And so $2\leq x_n\leq3$, $x_n$ is bounded and increasing, hence it converges. Therefore $\lim_{n \to \infty}x_n=e$.

The proof proceeds with proving that $\lim_{n\to \infty}y_n=Y$, and then showing $y\geq e$ and $y \leq e$, and thereby $y=e$. This part is very long and already looking messy in the notebook. Because of that I will skip it, since it isn't important for the question.

---

My questions:

1. Is there any obvious reason why $2^{n-1}$ is a good (necessary?) choice for the inequality (1.1)?

2. How does (1.2) follow from (1.1)? Why is it $\leq$ and not $ < $ ? I see that $\leq$ is the right choice since for $n=1$, we have $\frac{1}{1!}=\frac{1}{2^{1-1}}$, but is there any way to know this without evaluating for choices of $n$?

3. Why is that $2$ there in inequality (1.3)? Where did it come from ?

4. Considering inequality (1.4) there is few things;

   a) How was the overbraced fraction derived from the geometric series?

   b) The underbraced equality at first didn't make sense to me, but when I evaluated for few $n$s, I realized it actually holds. Is this a known thing, that the order of subracting isn't important for two fractions to be equal, as long as both the numerator and the denominator of the fraction are both $<0$ or $>0$? Also what was the role of the equality in the proof, or was it just a remark ?

   EDIT: I just realized that we can do that since the fraction is always positive. But it still doesn't seem so obvious to notice. Should it be obvious?

5. Why is that $1$ there in the inequality (1.5) ? Where did it come from ?

6. If you have a source for this proof please send me a link or tell me where I can find it.

Thanks

Answer 1

Question 1) we want

$x_n = 1 + \frac 1{1!} + \frac 1{2!} + ..... + \frac 1{n!} \le $

$1 + f(1) + f(2) + ...... + f(n) \le$

$1+F(n)$

where $F(n)$ is something bounded that we can manipulate.

$f(k) = \frac 1{2^{k-1}}$ and $F(n) = 1+ \frac 11+ \frac 12 + \frac 14 + ..... + \frac 1{2^{n-}}$ are good choices because $F(n) = 1+ \frac 11+ \frac 12 + \frac 14 + ..... + \frac 1{2^{n-1}}= 3-\frac 1{2^{n}}<3$ is a really easy calculation to make and prove, and proving that $\frac 1{n!} =\frac 1{2*3*4*5*....*n} \le \frac 1{2*2*2*.....*}=\frac 1{2^{n-1}}$ is equally easy.

If we can find find some other $f(k)$ and $F(n)$ and $K$ so that $\frac 1{n!} \le f(n)$ and that $1 + \sum_{k=1}^n f(k) = 1+ F(n) \le K$ we are free to use those but... powers of $2$ these choices are so easy.

Question 2:

$\le$ is weaker than $<$ and a stronger statement always implies a weaker statement.

$n! > 2^{n-1} \implies \frac 1{n!} < \frac 1{2^{n-1}} \implies \frac 1{n!} \le \frac 1{2^{n-1}}$.

That certainly isn't false.

But as to why we used $\le$ rather than $<$..... well, for the case when $n =1$ and $\frac 1{n!} = \frac 1{2^{n-1}}$. That's all. It's a one time exception.

Question 3:

It's just a lower bound. If $n = 1$ then $x_1 = 1 + \sum_{k=1}^1 \frac 1{k!} = 1+ \frac 1{1!} = 2$.

That's all.

Question 4:

It is a well known equality that for any $q\ne 1$ that $1 + q + q^2 + ..... + q^{n-1} = \frac {1-q^n}{1-q} = \frac {q^n -1}{q-1}$

$(1+q + q^2 + ..... + q^{n-1})(1-q)=$

$(1+q + q^2 + ..... + q^{n-1}) - q(1+q + q^2 + ..... + q^{n-1})=$

$(1+q + q^2 + ..... + q^{n-1}) - (q + q^2 + q^3 + ..... + q^{n})= $

$(1 + \underbrace{q^2 + ..... + q^{n-1}}) -(\underbrace{q^2 + ..... + q^{n-1}} + q^n) =$

$1-q^n$.

So if $(1+q + q^2 + ..... + q^{n-1})(1-q) = 1-q^n$ then $\frac {1-q^n}{1-q} = (1+q + q^2 + ..... + q^{n-1})$

"Is this a known thing, that the order of subracting isn't important for two fractions to be equal, as long as both the numerator and the denominator of the fraction are both <0 or >0"

Yes. It is a known thing: $\frac {a-b}{c-d} = \frac {a-b}{c-d}\frac {-1}{-1} = \frac {-(a-b)}{-(c-d)} = \frac {b-a}{d-c}$.

Question 5:

If $\color{green}{1 + q + q^2 + ..... + q^{n-1}} = \color{green}{\frac {q^n -1}{q-1}}$ then

$\color{red}1 + \color{green}{1 + q + q^2 + ..... + q^{n-1}} = \color{red}1 +\color{green}{\frac {q^n -1}{q-1}}$

And notice back in 1.3 we had

$x_n = \color{red}1 + \color{green}{1 + \frac 12 + \frac 1{4} + .... + \frac 1{2^{n-1}}}$

....

Maybe this is all to complicated.

I'd do it.

$1 + \frac 1{1!} + \frac 1{2!} + \frac 1{3!} + \frac 1{4!}+ ....... + \frac 1{n!} =$

$(1 + 1) + \frac 1{2} + \frac 1{2*3} + \frac 1{2*3*4} + ..... + \frac 1{2*3*4*....n}< $

$2 + \frac 1{2} + \frac 1{2*2} + \frac 1{2*2*2} + .... + \frac 1{2*2*2*....*2} =$

$2 + (\frac 12 + \frac 1{4} + \frac 1{8} + ...... + \frac 1{2^{n-1}})$.

Then I'd make one of my flying leaps that every one knows the things I used to know as a kid that $\frac 12 + \frac 1{4} + \frac 1{8} + ...... + \frac 1{2^{n-1}} = 1-\frac 1{2^n} < 1$ because everyone has heard of the jumping flea paradox so everyone has seen this in kindergarten, haven't they? No? .... Well, each time we add only half of what we need to get to $1$ so we never add enough to get to one so the sum has to be less than $1$, right? Because we never add enough to get to $1$.

So $2 + (\frac 12 + \frac 1{4} + \frac 1{8} + ...... + \frac 1{2^{n-1}})< 2 + 1=3$

That really is all this proof is saying.

The key issue is noting that $2*3*4*...... *n \le 2*2*2*2*....*2$. Everything else just falls into place.

Answer 2

1. $2^{n-1}$ is a good choice because of the series in (1.3)

2. I think that it is a typo. The correct is $n!\geq 2^{n-1}$, since for $n=1$, the equality holds. And for all the values, we know that $n!>2^{n-1}$. It is a classical exercise in Analysis (maybe Calculus too?) that the function $x!$ grows faster than $x^a$ for any real value of $a$. Try it :)

3. Remember that $x_n=1+\dfrac{1}{1!}+\cdots+\dfrac{1}{n!}$. For $n=1, x_1=2$, and for all other values for $n$, $x_n>2$. That's way $x_n\geq 2.$

4. (a) In general,

$$a+ar+\cdots+ar^{n-1}=a\dfrac{1-r^n}{1-r}. $$

There is several ways of proving this. For example, let $S_n=a+ar+\dots ar^n.$ Now evaluate $S_n-S_{n-1}$, and see what you got.

(b) Just multiply the numerator and the denominator by $(-1)$

5. It comes from "nowhere". It is the beginning of a new equation. It just uses the inequality in (1.4)

6. I don't know anyone :c

Answer 3

I'll try answer step by step:

1. $(1.1)$ is not true for $n=1$.

2. To obtain $(1.2)$ from $(1.1)$ use $\frac{1}{a} <\frac{1}{b}\Leftrightarrow b<a$ for non negative numbers.

3. For left side of $(1.3)$ we have that $x_1$ already contain 2, for right use $(1.2)$

4. There is formula for sum for first members of geometric progression

5. It is first member of $x_n$

6. Rudin W. - Principles of mathematical analysis-(1976) from page 63 have similar reasonings.