# How to approach convergence $n!/n^n$ to infinity [duplicate]

Possible Duplicate:
Proof for convergence of a given progression $a_n := n^n / n!$

Is it fair to attack this problem as follows.

$$\frac1n\cdot\frac2n\cdots\frac{n-1}n$$

And the limit law allows for multiplication of each individual limit term.

So as $1/n$ converges to $0$, $0\cdot\ldots = 0$.

This is perhaps too simple, but why not ?

Anyway, I think my reasoning is plaussible, may the rule only count for determinate sequences. 1/n makes part of the sequence. So. It converges to 0.

-

## marked as duplicate by robjohn♦, Benjamin Lim, Marvis, Alex Becker, Asaf KaragilaMay 11 '12 at 19:05

$$\frac{n!}{n^n}=\frac{\overbrace{n\cdot (n-1)\cdot\ldots\cdot 2\cdot 1}^{n\text{ times}}}{\underbrace{n\cdot n\cdot\ldots\cdot n}_{n\text{ times}}}.$$

Now $\underbrace{n\cdot (n-1)\cdot\ldots\cdot 2\cdot 1}_{n\text{ times}}=\underbrace{n\cdot (n-1)\cdot\ldots\cdot 2}_{n-1\text{ times}}\cdot 1<\underbrace{n\cdot\ldots\cdot n}_{(n-1)\text{ times}}=n^{n-1}$ for $n>2$. Hence $$\frac{n!}{n^n}<\frac{n^{n-1}}{n^n}=\frac{1}{n}$$ and $\lim_{n\to\infty}1/n=0$.

-

The product rule tells you that the limit of a product is the product of the limits when the number of terms in the product is fixed and finite. In your example, the number of terms in the product grows with $n$. This means it isn't the product of a finite number of sequences and so the product rule doesn't apply.

-

In the previous answers you have seen why your reasoning is not precise and you have even seen a solution for your problem. Given that you have asked a bunch of similar questions, I will try to give an answer which hopefully enables you to tackle other questions of that type in the future.

First of all if you have a sequence of quotients you might want to have a look at numerator and denominater seperately. This gives you $\infty/\infty$, whatever that means. Anyway this is not very helpful and tells us that basically anything can happen. The next question should be which of them (numerator and denomintor) grows "faster" (again some unprecise notion). If the numerator grows faster you will get convergence to $\infty$, if the denominator grows faster you will get convergence to zero and if they grow "equaly" fast you probably get a finite limit.

So what is our situation here? The numerator gets an extra factor of the from $n+1$ in each step. The denominator on the other hand gets an additional factor which is also $n+1$ and every existing factor is upgraded from $n$ to $n+1$. This gives us the information that the denominator appears to grow way faster and the sequence should converge to zero.

This intuition tells us that we should prove that the sequence indeed goes to zero. None of this intuition appears in a proper proof but I guess everybody makes some considerations of that kind before he/she actually starts computing.

But how do we make this precise. The idea is to find an estimation of your sequence by something bigger, which we understand better and which also goes to zero. One way of doing this is presented in @Michaels answer: The denominator is smaller than some power of $n$ with a lower exponent than the denominator.

Another way to do this (which makes a somewhat less harsh estimation, but is not necessarily better or anything) is to observe

$$n!\leq (\frac{n+1}{2})^n$$

The idea is here to take pairs of factors in $n!$ of the form $1\cdot n$, $2\cdot (n-1)$, $3\cdot (n-2)$... For each pair you see something like $$1\cdot n=(\frac{n+1}{2}-\frac{n-1}{2})(\frac{n+1}{2}+\frac{n-1}{2})\leq (\frac{n+1}{2})^2$$ and similar for each other pair. You will end up with $n$ factors of the form $\frac{n+1}{2}$. Hence we have $$\frac{n!}{n^n}\leq \frac{(\frac{n+1}{2})^n}{n^n}=2^{-n}(1+\frac1n)^n\to0\cdot e=0$$

The third way tries to make an even less harsh estimation. Ideas like this might be helpful in general, if your sequence doesn't converge to zero but some finite positive limit. We have seen above how our sequence changes in each step, namely $n$ factors in the denominator of the form $n$ are upgraded to $n$ factors of the form $n+1$. Following this idea you can show inductively that $$\frac{n^n}{n!}=\prod_{i=1}^{n-1}(\frac{i+1}{i})^i=\prod_{i=1}^{n-1}(1+\frac{1}{i})^i$$ (Note that I compute the reciprocal of our sequence). This looks somewhat like a product where infinitely many factors are very close to $e$. To make this precise: Let $\epsilon>0$ be fixed such that $e-\epsilon>1$. Then we find an $N$ such that $e>(1+\frac{1}{i})^i>e-\epsilon$ for all $i\geq N$. We then see for $n>N$ $$\frac{n^n}{n!}=\prod_{i=1}^{n-1}(1+\frac{1}{i})^i=\prod_{i=1}^{N-1}(1+\frac{1}{i})^i\cdot \prod_{i=N}^{n-1}(1+\frac{1}{i})^i\geq 1^{N-1}\cdot (e-\epsilon)^{n-N}\to \infty.$$

So the reciprocal goes to zero.

-

I believe that the "limit of a product" rule that you are trying to use is an extension of $$\lim_{n\to\infty}a_nb_n=\lim_{n\to\infty}a_n\lim_{n\to\infty}b_n\tag{1}$$ Inductively, $(1)$ can be extended to a product of any fixed number of terms. However, difficulty can arise when the number of terms is allowed to vary with $n$ as well. One common counterexample is $$\lim_{n\to\infty}\left(1+\frac1n\right)^n\tag{2}$$ Each term in this sequence consists of the product of $n$ copies of $\left(1+\frac1n\right)$, and $\lim\limits_{n\to\infty}\left(1+\frac1n\right)=1$. If we try to apply the "limit of a product" rule here, we would get a limit of $1$, when in actuality, the limit is $e$.

Viewing your product in reverse, we get $$\frac{n!}{n^n}=\frac{n}{n}\frac{n-1}{n}\frac{n-2}{n}\frac{n-3}{n}\dots\tag{3}$$ Rather than tending to $0$, each term in $(3)$ tends to $1$. As in $(2)$, this leads to an error.

One way around this is to consider the product of a fixed number, $k$, of terms in the product. We can use the fact that $[0,1]$ is closed under multiplication to handle the rest.

Note that for $n\ge k$, \begin{align} \frac{n!}{n^n} &=\left(\frac{n}{n}\frac{n-1}{n}\frac{n-2}{n}\dots\frac{k+2}{n}\frac{k+1}{n}\right)\frac{k!}{n^k}\\ &\le\frac{k!}{n^k}\tag{4} \end{align} Therefore, for any fixed $k$, \begin{align} \lim_{n\to\infty}\frac{n!}{n^n} &\le\lim_{n\to\infty}\frac{k!}{n^k}\\ &=0\tag{5} \end{align} Since $\dfrac{n!}{n^n}\ge0$, the Squeeze Theorem says that $\displaystyle\lim_{n\to\infty}\frac{n!}{n^n}=0$.

-

Because the limit law you mention allows for multiplication of each individual limit term whenever you can decompose your sequence into a fixed number of factors which does not depend on $n$.

-