5
$\begingroup$

In PoMA Rudin writes

Let $s_n=\sum_0^n \frac 1 {k!}$, $t_n=\left(1+\frac 1 n \right)^n$.

By the binomial theorem, $$t_n=1+1+\frac{1}{2!}\left(1 - \frac{1}{n}\right) + \frac{1}{3!}\left(1 - \frac{1}{n}\right)\left(1 - \frac{2}{n}\right) +\cdots+\frac 1 {n!}\left(1-\frac 1 n\right)\left(1-\frac 2 n\right)\cdots \left(1-\frac {n-1} n\right).$$

Hence $t_n\leq s_n$, so that $\limsup t_n\leq e$.

Next, if $n\geq m$,

$$ t_n\geq 1+1+\frac 1 {2!}\left(1-\frac 1 n\right)+\cdots \frac 1 {m!}\left(1-\frac 1 n\right)\cdots\left(1-\frac {m-1} n\right). $$

Keeping $m$ fixed and letting $n\to \infty$. We get $$\liminf t_n \geq 1+1+\frac 1 {2!}+\cdots \frac {1}{m!}.$$

So that $s_m\leq \liminf t_n$. Letting $m\to \infty$ we get that $e\leq \liminf t_n$.

I'd like to remove all the $\,\cdots$'s as I'm a bit allergic to them (first to justify the claim that $t_n\leq s_n$, and then the "if $n\geq m$ then..." part).

I couldn't do this myself, so I ask for your help. Thanks!

$\endgroup$
2

4 Answers 4

13
$\begingroup$

It wouldn't have killed Rudin to write a few more details in this proof. I don't like writing in my books, but I finally broke down and wrote a few lines of explanation in my copy, after my second or third experience of looking up this proof and forgetting why it worked.


The structure of the proof is to show that $$\limsup_{n \to \infty}t_n \leq e \leq \liminf_{n \to \infty}t_n$$ Since we always have $\liminf \leq \limsup$, the above inequality implies that $$\liminf_{n \to \infty}t_n = \limsup_{n \to \infty}t_n = e$$ and therefore the limit $\lim_{n \to \infty}t_n$ exists and equals $e$.
The first step is to prove that $$\limsup_{n \to \infty}t_n \leq e$$

A minor detail: you have miscopied slightly. Comparing with Rudin, your term $$\frac{1}{2!}\left(1 - \frac{1}{n}\right)\left(1 - \frac{2}{n}\right)$$ should instead be these two terms: $$\frac{1}{2!}\left(1 - \frac{1}{n}\right) + \frac{1}{3!}\left(1 - \frac{1}{n}\right)\left(1 - \frac{2}{n}\right)$$ Let us see how to obtain an expression without ellipses: $$\begin{aligned} t_n &= \left(1 + \frac{1}{n}\right)^n \\ &= \sum_{k=0}^{n}{n \choose k} 1^{n-k} \left(\frac{1}{n}\right)^{k}\\ &= \sum_{k=0}^{n}\frac{n!}{k!(n-k)!}\left(\frac{1}{n}\right)^k\\ &= \sum_{k=0}^{n}\frac{1}{k!}\left(\prod_{j=0}^{k-1}(n-j)\right)\left(\frac{1}{n}\right)^k \\ &= \sum_{k=0}^{n}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\frac{n-j}{n}\right) \\ &= \sum_{k=0}^{n}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right) \\ \end{aligned}$$ In the last line, note that the $j=0$ term in the product is $1$, which is why Rudin only needs to write $k-1$ factors of the form $\left(1 - \frac{j}{n}\right)$ in his $k$'th term. Also note that the $k=0$ and $k=1$ terms are simply $1$. (We use the standard convention that the empty product in the $k=0$ term, $\displaystyle\prod_{j=0}^{0-1}$, is equal to $1$.)

Since each factor $\left(1 - \frac{j}{n}\right)$ is $\leq 1$, the $k$th term in the sum is $\leq 1/(k!)$, which gives us $$t_n \leq \sum_{k=0}^{n}\frac{1}{k!} = s_n$$ We can take the limsup of both sides of this inequality to conclude that $$\limsup_{n \to \infty} t_n \leq \limsup_{n \to \infty} s_n = \lim_{n \to \infty}s_n = e$$


The next step is to show that $$e \leq \liminf_{n \to \infty}t_n$$ Observe that the terms in the sum $$t_n = \sum_{k=0}^{n}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right)$$ obtained above are all nonnegative, so $t_n$ is at least as large as the sum of the first $m$ terms ($m \leq n$): $$t_n \geq \sum_{k=0}^{m}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right)$$ which is the second expression given by Rudin. The right-hand side depends on both $m$ and $n$. For convenience, let's give it a name: $$a_{m,n} = \sum_{k=0}^{m}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right)$$ So our inequality is simply $$t_n \geq a_{m,n}$$ Let us now consider what happens if we hold $m$ fixed and take $n \to \infty$. We focus on the right hand side.

First, observe that $0 \leq j \leq k-1$, and $0 \leq k \leq n$, which means that $0 \leq j \leq n-1$. Therefore $$\lim_{n \to \infty}\left(1 - \frac{j}{n}\right) = 1$$ Now, observe that $m$, $j$, and $k$ do not depend on $n$, so the limit of the product is the product of the limits of the factors: $$\lim_{n \to \infty}\prod_{j=0}^{k-1} \left(1 - \frac{j}{n}\right) = \prod_{j=0}^{k-1}\left[ \lim_{n \to \infty} \left(1 - \frac{j}{n}\right) \right] = \prod_{j=0}^{k-1} [1] = 1$$ Similarly, the limit of the sum is the sum of the limits of the terms, so $$\begin{aligned} \lim_{n \to \infty}a_{m,n} &= \lim_{n\to\infty}\sum_{k=0}^{m}\frac{1}{k!}\left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right)\\ &= \sum_{k=0}^{m}\frac{1}{k!} \left[\lim_{n \to \infty} \left(\prod_{j=0}^{k-1}\left(1 - \frac{j}{n}\right)\right]\right) \\ &= \sum_{k=0}^{m} \frac{1}{k!}[1] \\ &= \sum_{k=0}^{m} \frac{1}{k!} \\ &= s_m \\ \end{aligned}$$ This shows that the limit of the right hand side of the inequality $$t_n \geq a_{m,n}$$ exists as $n \to \infty$. We don't yet know that the limit of the left hand side exists. But certainly we can take the liminf of both sides to obtain $$\liminf_{n \to \infty}t_n \geq \liminf_{n \to \infty} a_{m,n} = \lim_{n \to \infty}a_{m,n} = s_m$$ where we have used the fact shown above that $\lim_{n \to \infty}a_{m,n}$ exists and equals $s_m$. Then, as Rudin indicates, we can take the limit of the right hand side as $m \to \infty$ (the left hand side does not depend on $m$), to conclude that $$\liminf_{n \to \infty}t_n \geq \lim_{m \to \infty}s_m = e$$ This concludes the proof.

$\endgroup$
5
  • $\begingroup$ "It wouldn't have killed Rudin to write a few more details in this proof" - heh... $\endgroup$
    – Math1000
    Mar 25, 2016 at 1:56
  • 3
    $\begingroup$ @Math1000 :-) Some people would say that the same applies to all of Rudin's proofs, but I think this one is especially annoying in that regard. $\endgroup$
    – user169852
    Mar 25, 2016 at 2:06
  • $\begingroup$ I really agree :-P. One question, on the line after the $(m\leq n)$ part, why can you take $\lim_n$? After that, why does $$\lim_n \sum_{k=0}^m \frac {1}{k!}\left(\prod_{j=0}^{k-1}\left(1-\frac j n\right)\right) = \sum_{k=0}^m \frac {1}{k!}\left(\prod_{j=0}^{k-1}\lim_n\left(1-\frac j n\right)\right) $$? $\endgroup$ Mar 25, 2016 at 2:42
  • 1
    $\begingroup$ @YoTengoUnLCD: I added some extra detail which will hopefully clarify things. $\endgroup$
    – user169852
    Mar 25, 2016 at 4:08
  • $\begingroup$ Excellent answer @Bungo, thanks! $\endgroup$ Mar 25, 2016 at 16:05
4
$\begingroup$

Since $$t_n:=\left(\frac1n+1\right)^n=\sum_{k=0}^n{n\choose k}\left(\frac1n\right)^k1^{n-k}=\sum_{k=0}^n{n\choose k}\left(\frac1n\right)^k,$$ the assertion $t_n\le s_n$ follows from the fact that $${n!\over k!(n-k)!}\frac1{n^k}\le\frac1{k!}$$ which is a restatement of the fact $$n!\le n^k(n-k)!.$$ As for the next step, we have for each $m$: if $n\ge m$, then $$ t_n=\sum_{k=0}^n{n\choose k}\left(\frac1n\right)^k\ge\sum_{k=0}^m{n\choose k}\left(\frac1n\right)^k.\tag1 $$ The $k$th term on the RHS can be written $$\frac1{k!}{n!\over(n-k)!}\frac1{n^k}.\tag2 $$ The assertion is that this tends to $\frac1{k!}$ as $n\to\infty$. To see this is true, set aside the $1/k!$. Note that $n!/(n-k)!$ is a product of $k$ terms of the form $n-j$, with $j$ ranging from $0$ to $k-1$. Similarly, the denominator $n^k$ is a product of $k$ copies of $n$. Match these up to obtain a product of $k$ ratios, each one of which tends to $1$ as $n\to\infty$, hence their product also tends to $1$, leaving $\frac1{k!}$.

Remember that we are treating $m$ as fixed throughout this step, so it is legitimate to take the limit (as $n\to\infty$) of the rightmost sum in (1) term by term. Likewise, it is legitimate to take the limit of the product (2) term by term, since you have at most $m$ factors in (2) that involve $n$.

$\endgroup$
2
  • $\begingroup$ Could you prove the last fact (or give some hints on how to?)? I attempted to prove it by induction but I failed. $\endgroup$ Mar 25, 2016 at 1:17
  • $\begingroup$ I've edited my answer to expand on the last step. $\endgroup$
    – grand_chat
    Mar 25, 2016 at 5:27
2
$\begingroup$

Define $$ s_m(z) = \sum_{j=0}^m \frac{z^j}{j!}, t_m(z) = \left(1 + \frac{z}{m}\right)^m $$ We wish to show that $\lim_{j \to \infty} s_m(z) = \lim_{j \to \infty} t_m(z)$ for all $z \in \mathbb{C}$. By the Binomial Theorem, $$\begin{align*} t_m(z) &= \sum_{j=0}^m \binom m j 1^{m-j} \left(\frac z m\right)^j = \sum_{j=0}^m \frac{m!}{j!(m-j)!} \frac{z^j}{m^j} \\ &= \sum_{j=0}^m \frac{m!}{m^j(m-j)!} \frac{z^j}{j!} \leq s_m(z) \end{align*}$$ Since $m!/(m^j(m-j)!) \leq 1$. Hence $\limsup_{m \to \infty} t_m(z) \leq \limsup_{m \to \infty} s_m(z)$.

$\endgroup$
2
  • $\begingroup$ What do you mean by $\limsup s_m(z) =\exp z$ follows from Cauchy-Hadamard? You're only talking about the radius of convergence? (As $s_m(z) \to \exp z$ is the usual definition of $\exp$). $\endgroup$ Mar 25, 2016 at 0:21
  • $\begingroup$ @YoTengoUnLCD Yes. I will make it clear $\endgroup$ Mar 25, 2016 at 0:22
1
$\begingroup$

The hard part of the proof seems to be to show that if $k < n$ then $\lim_{n \to \infty}\prod_{j=0}^{k-1}\left(1-\frac j n\right) =1 $.

I would do it using this lemma:

If $x_k > 0$ and $\sum_{k=1}^n x_k < 1 $, then $\prod_{i=1}^k (1-x_i) \ge 1-\sum_{i=1}^k x_i $ for $1 \le k \le n $.

The proof, of course, is by induction.

It is true for $k=1$.

If it true for $k$, then

$\begin{array}\\ \prod_{i=1}^{k+1} (1-x_i) &=(1-x_{k+1})\prod_{i=1}^{k} (1-x_i)\\ &\ge (1-x_{k+1})(1-\sum_{i=1}^{k} x_i)\\ &=1- \sum_{i=1}^{k+1} x_i +x_{k+1}\sum_{i=1}^{k} x_i\\ &\ge 1- \sum_{i=1}^{k+1} x_i \\ \end{array} $

Now consider $p(k, n) = \prod_{j=0}^{k-1}\left(1-\frac j n\right) $.

If $\sum_{j=0}^{k-1} \frac j n < 1 $, we can apply the lemma. But this is equivalent to $n > \frac{k(k-1)}{2} $, which is certainly true for $n > k^2 $.

The next step is to make the product arbitrarily close to $1$ by making $n$ even larger.

If $n > k^2$,

$\begin{array}\\ p(k, n) &=\prod_{j=0}^{k-1}\left(1-\frac j n\right)\\ &\ge 1-\sum_{j=0}^{k-1}\left(\frac j n\right)\\ &\ge 1-\frac{k(k-1)}{2n}\\ &\gt 1-\frac{k^2}{n}\\ \end{array} $

So if we choose $n > k^3$, $p(k, n) \gt 1-\frac{(n^{1/3})^2}{n} = 1-\frac1{n^{1/3}} $ and we can make this arbitrarily close to $1$ by making $n$ large enough.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .