Skip to main content

Derive e

Prove that \( \left( 1 + \frac{1}{n} \right)^n \) converges.

Solution

Let \( G(n) =  \left( 1 + \frac{1}{n} \right)^n \).

Binomial expansion, \( G(n) = \sum_{k = 0}^{n} \frac{ \binom{n}{k} }{n^k} \).

By simple inequality argument, \( \frac{ \binom{n}{k} }{n^k} < \frac{1}{k!} \).

So if we let \( F(n) = \sum_{k = 0}^{n} \frac{1}{k!} \), we have \( G(n) < F(n) \).

By simple inequality argument, \( F(n) < 1 + \sum_{k = 1}^{n} \frac{1}{2^{k-1}} < 3 \).

So G and F are bounded above.

By AM-GM, \( \frac{G(n-1)}{G(n)} = \left( \frac{ n^2 }{ n^2 - 1} \right)^{(n-1)} \frac{ n}{n+1} < \left(  \frac{ \frac{ n^2 }{ n^2 - 1} (n-1) + \frac{ n}{n+1} }{n} \right)^n = 1 \). So \( G(n-1) < G(n) \).

Since G is monotonic increasing and bounded above, G converges.

Similarly F converges.

Let's also prove that G and F converges to the same limit.

By studying individual terms in \( F(n) - G(n) \) and making simple inequality arguments, we can show that for each \( \epsilon > 0 \) we can pick N s.t. \( F(n) - G(n) < \epsilon \) for all n > N. This can be further used to make the formal argument that the limit of F is the same as the limit of G.

So if we call the limit e, then \( \lim_{n \to \infty } \left( 1 + \frac{1}{n} \right) ^n  = 1 + \frac{1}{1!} + \frac{1}{2!} +  \frac{1}{3!} + \cdots = e \).

Comments

Post a Comment

Popular posts from this blog

641 | 2^32 + 1

Problem: Show that \( 641 | 2^{32} + 1 \). Solution: (From Problem Solving Strategies, Arthur Engel) \( 641 = 625 + 16 = 5^4 + 2^4 \). So \( 641 | 2^{32} + 2^{28} \cdot 5^4 \). Also, \( 641 = 640 + 1 = 2^7 \cdot 5 + 1\). So \( 641 | (2^7 \cdot 5)^4 - 1 = 2^{28}\cdot 5^4 - 1 \). Hence \( 641 | 2^{32} + 2^{28} \cdot 5^4 -(2^{28}\cdot 5^4 - 1) \). QED
Post a Comment
Read more

Derive Poisson Distribution

Let's say we are observing an event that to us seems random. E.g. The number of cars passing through a road. Suppose we learn that on average, there are m cars passing the road within 1 hour. Goal: Can we make a model to suggest what is the probability of seeing exactly r cars passing the road in an hour? Let's represent one hour as a line, and on the line there are marks to represent the time on which a car passes. Let's suppose there are m marks, to represent the average case of seeing m cars on the road in an hour. Let's divide the 1 hour line into n uniform time segments, n large enough such that in one time segment there is at most 1 car. Out of the n time segments, m of them contains a car. Then it is reasonable to say that the probability of a time segment to contain a car is m/n. Let's analyse as n goes to infinity. We can say P(seeing exactly r cars in an hour) =  P(exactly r cars contained in n segments) = \( \binom{n}{r} \left( \frac{m}{n} \right)^r \left...
Post a Comment
Read more

n-th non-square

Problem: Find the n-th non-square number. (Adapted from Problem Solving Strategies, Arthur Engel ) If you have CS background, I invite you to come up with an O(log N) solution. Done? Good. Below I present the O(1) approach. Solution: The n-th non-square number is given by \( F(n) = \left \lfloor n + \sqrt{n} + 1/2  \right \rfloor \). Proof: Let G(n) be the same as F(n) except for the floor function. Investigate \( m \neq F(n) \). There is the largest \( n \) s.t. \( F(n) < m \). Hence \( m+1 \leq F(n+1) \). We conclude that \(G(n) < m \) and \(m+1 \leq G(n+1) \). Rearranging the terms and squaring the inequalities, we get: \( n < (m-n-1/2)^2 \) and \( (m-n-1/2)^2 < n+1 \), or \( n - 1/4 < (m-n)^2 - (m-n) < n + 3/4 \). Since the middle term is an integer, we see that \( (m-n)^2 - (m-n) = n \). Simplifying, we get \(m = (m-n)^2\), showing that m is a square. In other words, F(n) skips all squares. Now, we will show that F(n) is the n-th non...
Post a Comment
Read more