# Evaluation of limit without using Stirling's approximation

I'm trying to find a way to show that $\lim_{n\to+\infty} \frac{n!e^{n}}{n^{n}}=+\infty$ without using Stirling's approximation. I tried a few things that didn't work, any help would be appreciated. (I came across this limit the following way: we all know that $\lim_{n\to+\infty} \frac{n!}{n^{n}}=0$ the next obvious thing to try is $\lim_{n\to+\infty} \frac{n!a^{n}}{n^{n}}$. By the ratio criterium for sequences $\frac{n!a^{n}}{n^{n}}$ goes to $+\infty$ if $a>e$ and to $0$ if $a<e$ so it's natural to wonder what happens with $a=e$. Using Stirling it's obvious but I wanted to be able to present this in a more elementary fashion if needed)

• Why the -1? Is this not an appropriate question for this site? Feb 6, 2018 at 7:50

Let us denote

$$a_n = \frac{n!e^n}{n^n}.$$

Method 1. The ratio between the adjacent terms is given by

$$\frac{a_{n+1}}{a_n} = \frac{e}{\left(1+\frac{1}{n}\right)^n}$$

Taking logarithm, we have

$$\log a_{n+1} - \log a_n = 1 - n \log\left(1+\frac{1}{n}\right) = \int_{0}^{1} \frac{x}{n+x} \, dx \geq \frac{1}{2(n+1)}.$$

So it follows that

$$\log a_n \geq \log a_1 + \sum_{k=2}^{n} \frac{1}{2k} \qquad \Rightarrow \qquad a_n \geq \exp\left(1+ + \sum_{k=2}^{n} \frac{1}{2k}\right)$$

which diverges as $n\to\infty$.

Method 2. We know that $\left(1+\frac{1}{n}\right)^n$ increases to $e$. So

$$\frac{a_{n+1}}{a_n} = \frac{e}{\left(1+\frac{1}{n}\right)^n} \geq \frac{\left(1+\frac{1}{2n}\right)^{2n}}{\left(1+\frac{1}{n}\right)^n} = \left(1 + \frac{1}{4n(n+1)}\right)^n \geq 1 + \frac{1}{4(n+1)},$$

where the last step follows from Bernoulli's inequality: $(1 + h)^n \geq 1 + nh$ for $n \geq 1$ and $h > 0$. So we have

$$a_{n} = a_1 \prod_{k=2}^{n} \frac{a_k}{a_{k-1}} \geq \prod_{k=2}^{n} \left(1 + \frac{1}{4k} \right) \geq 1 + \sum_{k=2}^{n} \frac{1}{4k}.$$

Therefore $a_n$ diverges by the comparison test.

Method 3. If you are allowed to use the Taylor expansion $e^x = \sum_{k=0}^{\infty} \frac{x^k}{k!}$, then

$$a_n = \frac{n!}{n^n} \sum_{k=0}^{\infty} \frac{n^k}{k!} \geq \frac{n!}{n^n} \sum_{k=n}^{n+\lfloor \sqrt{n}\rfloor} \frac{n^k}{k!} = \sum_{j=0}^{\lfloor \sqrt{n}\rfloor} \frac{n^j}{(n+1)\cdots(n+j)}.$$

Now notice that for $0 \leq j \leq \sqrt{n}$,

$$\frac{(n+1)\cdots(n+j)}{n^j} \leq \frac{(n+j)^j}{n^j} = \left(1+\frac{j}{n}\right)^j \leq \left(1+\frac{\sqrt{n}}{n}\right)^{\sqrt{n}} = \left(1+\frac{1}{\sqrt{n}}\right)^{\sqrt{n}}.$$

This gives the following lower bound

$$a_n \geq \frac{\sqrt{n}}{\left(1+\frac{1}{\sqrt{n}}\right)^{\sqrt{n}}}$$

which obviously diverges as $n\to\infty$.

• Thak you Sangchul. Let me process this. Feb 5, 2018 at 13:34
• Nice! I like method 2 because it's very elementary. I definitely would not think of using the estimate $e > \left(1+\frac{1}{2n}\right)^{2n}$, althought it makes a lot of sense with hindsight. Also the next argument shows in general that if $\liminf n\left(\frac{a_n+1}{a_n}-1\right)>c>0$ then $a_n$ goes to $+\infty$, right? Feb 5, 2018 at 20:07
• @GonçaloMarques Glad you like it! And yes, that’s right. :) Feb 5, 2018 at 20:52
• On method 1 you used the so called second mean value theorem for calculus to establish $\int_{0}^{1} \frac{x}{n+x} \, dx \geq \frac{1}{2(n+1)}$ right? Of course it makes sense to use an integral since you are dealing with logarithms but the representation $1 - n \log\left(1+\frac{1}{n}\right) = \int_{0}^{1} \frac{x}{n+x} \, dx$ it's so nice and simple. Well done! Feb 6, 2018 at 8:04
• @GonçaloMarques, It is much simpler than that, as you can bound the integrand by $\frac{x}{n+x} \geq \frac{x}{n+1}$. As a side note, the first method is in some sense better than others because it provides a very cheap way of showing that $n! \sim C\sqrt{n} \cdot n^{n} e^{-n}$ as $n\to\infty$ for some positive constant $C > 0$. Feb 6, 2018 at 14:12

$\newcommand{\P}{\mathbb P}$Somehow an overkill, but the probabilistic method cannot be left untouched (almost surely). Let $X_i \sim \text{Poi}(1)$ i.i.d. Since $X_1+...+X_n\sim\text{Poi}(n)$, we have: \begin{align} \frac{n^n}{n!e^n}=\P(X_1+...+X_n = n)>0 \end{align} Let $\varepsilon>0$ \begin{align} \P(X_1+...+X_n = n)&=\P\left(\frac{X_1+...+X_n-n}{\sqrt[]{n}}=0\right)\\ &\leq \P\left(-\varepsilon\leq \frac{X_1+...+X_n-n}{\sqrt[]{n}} \leq \varepsilon\right) \end{align} Use the Central Limit Theorem to conclude: \begin{align} \lim_{n\to\infty}\P\left(-\varepsilon\leq \frac{X_1+...+X_n-n}{\sqrt[]{n}} \leq \varepsilon\right) = \Phi(\varepsilon)-\Phi(-\varepsilon) \end{align} where $\Phi(\cdot)$ is the CDF of standard normal. Take $\varepsilon\to 0$ to conclude: \begin{align} \lim_{n\to \infty}\P(X_1+...+X_n=n)=0 \end{align} Since $\P(\cdot)\geq 0$ we get: \begin{align} \lim_{n\to \infty}\frac{n!e^n}{n^n}=\lim_{n\to\infty}\frac{1}{\P(X_1+...+X_n=n)}=\infty \end{align}

• Thanks Shashi. Just so I get started on this: what's a random variable with Poi(1) distribution? Feb 5, 2018 at 15:19
• @GonçaloMarques poisson distribution with parameter $1$ Feb 5, 2018 at 15:20

In a elementary fashion, $m=\prod_{k=1}^{m-1}\left(1+\frac{1}{m}\right)$ leads to $$n! = \prod_{m=2}^{n}m=\prod_{m=2}^{n}\prod_{k=1}^{m-1}\left(1+\frac{1}{k}\right)=\prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right)^{n-k}= \frac{n^{n}}{\prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right)^k}$$ and since $\left\{\left(1+\frac{1}{k}\right)^{k+\frac{1}{4}}\right\}_{k\geq 1}$ is increasing and convergent towards $e$, $$n! = \frac{n^{n+\frac{1}{4}}}{\prod_{k=1}^{n-1}\left(1+\frac{1}{k}\right)^{k+\frac{1}{4}}}\geq \frac{n^{n+\frac{1}{4}}}{e^{n-1}}$$ and $$\frac{n!e^n}{n^n}\geq e\sqrt{n}\to +\infty.$$

• One think that is not clear to me is why $\left\{\left(1+\frac{1}{k}\right)^{k+\frac{1}{4}}\right\}_{k\geq 1}$ is increasing . Obviously $\left\{\left(1+\frac{1}{k}\right)^{k}\right\}_{k\geq 1}$ is increasing but $\left\{\left(1+\frac{1}{k}\right)^{\frac{1}{4}}\right\}_{k\geq 1}$ is decreasing Feb 5, 2018 at 15:16
Since \begin{align} (k-1)\log\left(1+\frac1{k-1}\right) &=(k-1)\int_0^{\frac1{k-1}}\frac{\mathrm{d}x}{1+x}\\ &\le(k-1)\int_0^{\frac1{k-1}}\left(1-x+x^2\right)\,\mathrm{d}x\\ &=1-\frac1{2(k-1)}+\frac1{3(k-1)^2}\tag1 \end{align} we have $$1+(k-1)\log\left(1-\frac1k\right) \ge\frac1{2(k-1)}-\frac1{3(k-1)^2}\tag2$$ Therefore, since $$\frac{\frac{n!\,e^n}{n^n}}{\frac{(n-1)!\,e^{n-1}}{(n-1)^{n-1}}} =e\left(\frac{n-1}n\right)^{n-1}\tag3$$ we have \begin{align} \frac{n!\,e^n}{n^n} &=e\prod_{k=2}^ne\left(1-\frac1k\right)^{k-1}\tag4\\ &=\exp\left[1+\sum_{k=2}^n\left(1+(k-1)\log\left(1-\frac1k\right)\right)\right]\tag5\\[3pt] &\ge\exp\left[1+\frac12H_{n-1}-\frac13\frac{\pi^2}6\right]\tag6\\[7pt] &\ge e^{1+\frac\gamma2-\frac{\pi^2}{18}}\sqrt{n-1}\tag7\\[18pt] &\ge2\sqrt{n-1}\tag8 \end{align} Explanation:
$(4)$: induction on $(3)$
$(5)$: write the product as the exponential of a sum
$(6)$: apply $(2)$
$(7)$: $H_n\ge\log(n)+\gamma$ where $\gamma$ is the Euler-Mascheroni Constant
$(8)$: $e^{1+\frac\gamma2-\frac{\pi^2}{18}}\gt2$