# Homework Help: Unable to prove e without math. induction

1. Mar 20, 2009

### soopo

1. The problem statement, all variables and given/known data
How can you prove the following statement without mathematical induction?
$$lim_{n -> \infty} (1 + \frac {1} {n})^{n} = \sum_{n=0}^{\infty} \frac {1} { n! }$$

3. The attempt at a solution

The statement can be proven by mathematical induction, but I am interested in how the sum statement can be deduced.

2. Mar 20, 2009

### Dick

I'd be interested in how you prove that with induction. But try expanding (1+1/n)^n in a binomial expansion and look at the limit of the individual terms.

3. Mar 20, 2009

### soopo

Let's consider only the first three and the last three terms in the binomial expansion
$$1 + (n,1) \frac {1} {n} + (n,2) \frac {1} {n^{2}} + (n,3) \frac {1} {n^{3}} + ... + (n, n-3) \frac {1} {n^{n-3}} + (n, n-2) \frac {1} {n^{n-2}} + (n, n-1) \frac {1} {n^{n-1}} + \frac {1} {n^{n}}$$

where (n,n) is a combination, for instance.
(n,0) and (n,n) are one.

Perhaps, I should now factorise by $$\frac {1} {n}$$.

4. Mar 20, 2009

### Dick

Look at a single term, e.g. (n,3)/n^3. Expand (n,3) in factorials. Cancel some terms in the numerator and denominator. Can you see what happens?

5. Mar 22, 2009

### soopo

$$1 + n (\frac {1}{n})^{1}) + n(n - 1) \frac {1}{2!} (\frac {1}{n})^{2}) + n(n - 1)(n - 2) \frac {1}{3!} (\frac {1}{n})^{3}) + ... + n(n - 1)(n - 2) \frac {1}{3!} (\frac {1}{n})^{n-3}) + n(n - 1) \frac {1}{2!} (\frac {1}{n})^{n-2}) + n (\frac {1}{n})^{n-1}) + \frac {1} {n^{n}}$$

Simplifying
$$2(1 + 1 + \frac {n - 1}{n} \frac {1}{2!} + (n - 1)(n - 2) \frac {1}{n^{2}*3!} + ... ) + \frac {1} {n^{n}}$$

The series diverges, since n is a positive integer.

We should somehow be able to get the sum notation.

Last edited: Mar 22, 2009
6. Mar 22, 2009

### Dick

You are forgetting the 1/n^k part. For the term containing 3! I get
(n)(n-1)(n-2)/(n^3*3!). What's the limit of that as n->infinity?

7. Mar 22, 2009

### soopo

I get
$$\frac {1 - 3/n - 2/n^2} {3!} => 1/3!,$$
as n goes to infinity.

We should now apply the result for the rest of the terms.

Last edited: Mar 22, 2009
8. Mar 22, 2009

### Dick

n/n->1. (n-1)/n->1. (n-2)/n->1. As n->infinity. I get that the limit is 1/3!. Your limit also goes to 1/3!. In spite of a sign error.

9. Mar 22, 2009

### soopo

I agree with you.

I tried to prove the statement unsuccessfully by the proof of contradiction.
Nevertheless, if we can show that for n = 4 that the sum is 1/4!, we can apparently use mathematical induction to prove the statement.

I do not see any other way to prove the statement.

10. Mar 22, 2009

### Dick

The sum isn't 1/3!. A single term converges to 1/3!. You may be confused because the n on the right side of the equation has nothing to do with the n on the left. Try proving lim n->infinity (1+1/n)^n=sum k=0 to infinity 1/k!.

11. Mar 22, 2009

### soopo

Thank you for the clarification!
I had an idea that there is a relation between n's at both sides.

The binomial expansion is finally
$$2 + \frac{n-1}{n*2!} + ... + \frac {1}{n^n}(\frac {n^3(n-1)} {2!} + n^2 + 1)$$

We know that each of the coefficients such as n/n -> 1, (n-1)/n -> 1 and (n-2)/n -> 1, as n goes to infinity.
In contrast, the other end of the sequence converges to zero.
1/n^n -> 0, n^(2-n) -> 0, and n^(3-n)(n-1)/2! -> 0,
as n goes to infinity.

We get the following sequence
$$1 + 1 + 1/2! + 1/3! + ...$$

Each term in the sequence is in line with the LHS of the equation.
This completes the proof.

---
Is the proof correct?

12. Mar 22, 2009

### sutupidmath

Sorry for entering without permition, for i will not be that helpful either. But, without directly using induction, then it can be shown that:

$$\lim_{n\rightarrow \infty}\left(1+\frac{1}{n}\right)^n=e$$

And also, from the expansion of $$f(x)=e^x$$ using Taylor series around zero, and also letting x=1, we get

$$e=1+\frac{1}{1!}+\frac{1}{2!}+...=\sum_{n=0}^{\infty}\frac{1}{n!}$$

so from these two results we have that they are equal.

13. Mar 22, 2009

### Dick

I think so. Each term in binomial expansion (n,k)*(1/n)^k converges to 1/k!. So it's plausible that the sum converges to the sum of 1/k! which is e. It's not horribly rigourous, but I've guessing that's what you are supposed to come up with.

14. Mar 22, 2009

### Dick

All true. But I think this 'proof' maybe supposed to bypass the knowledge that lim n->infinity (1+1/n)^n=e.

15. Mar 23, 2009

### soopo

How would you do the proof more rigorous?

16. Mar 23, 2009

### Dick

You'd have to come with with some kind of error estimate for the sum of all of the parts that still contain n. But I wouldn't bother, because as stupidmath said, you know the limit is e and you know that the sum of 1/k! is also a convergent series summing to e from the Taylor series expansion of e^x.

17. Mar 23, 2009

Here is your rigorous proof. Using L'Hôpital's Rule,

$$Let y = lim_{n\rightarrow\infty}\left(1+\frac{1}{n}\right)^{n}$$

Take the natural logarithm of both sides of this equation.

$$ln(y) = ln\left[lim_{n\rightarrow\infty}\left(1+\frac{1}{n}\right)^{n}\right]$$

$$= lim_{n\rightarrow\infty}\left[ln\left(1+\frac{1}{n}\right)^{n}\right]$$

$$= lim_{n\rightarrow\infty}\left[nln\left(1+\frac{1}{n}\right)\right]$$

$$= lim_{n\rightarrow\infty}\left[\frac{ln \left(1+\frac{1}{n}\right)}{\frac{1}{n}}\right]$$

If we try to solve the above limit using direct substitution, we'll obtain the indeterminant form $$0/0$$. Thus, we apply L'Hôpital's Rule to attempt to find the limit by taking the derivative of the numerator and denominator and finding the limit of that ratio.

$$ln(y) = lim_{n\rightarrow\infty}\left[ln\left(\frac{1+\frac{1}{n}}{\frac{1}{n}}\right)\right]$$

$$= lim_{n\rightarrow\infty}\left[\left(\frac{-1/n^{2}}{1+\frac{1}{n}}\right)/\left(-1/n^2\right)}\right]$$

$$= lim_{n\rightarrow\infty}\left[1+\frac{1}{n}\right]$$
$$= 1$$

Therefore $$ln(y) = 1$$ which implies y = e by definition of logarithms.

By comparison, since we let y = the original limit expression, then:

$$e = lim_{n\rightarrow\infty}\left(1+\frac{1}{n}\right)^{n}$$

This completes the proof and shows why y converges to e as n gets larger and larger (approaches $$\infty$$).

18. Mar 23, 2009

### soopo

There is perhaps something wrong in the statements following the expression

$$ln(y) = lim_{n\rightarrow\infty}\left[ln\left(\frac{1+\frac{1}{n}}{\frac{1}{n}}\right)\right]$$

The problem seems to be in the derivate.
I get
$$ln(y) = lim_{n\rightarrow\infty}\left[\left(\frac {1/n} {1 + \frac{1}{n}})\right]$$