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)
4 Answers
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$.
-
$\begingroup$ Thak you Sangchul. Let me process this. $\endgroup$ Feb 5, 2018 at 13:34
-
$\begingroup$ 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? $\endgroup$ Feb 5, 2018 at 20:07
-
$\begingroup$ @GonçaloMarques Glad you like it! And yes, that’s right. :) $\endgroup$ Feb 5, 2018 at 20:52
-
$\begingroup$ 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! $\endgroup$ Feb 6, 2018 at 8:04
-
$\begingroup$ @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$. $\endgroup$ 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}
-
$\begingroup$ Thanks Shashi. Just so I get started on this: what's a random variable with Poi(1) distribution? $\endgroup$ Feb 5, 2018 at 15:19
-
$\begingroup$ @GonçaloMarques poisson distribution with parameter $1$ $\endgroup$– ShashiFeb 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[4]{n}\to +\infty.$$
-
$\begingroup$ Thanks Jack, let me think about this. $\endgroup$ Feb 5, 2018 at 13:40
-
$\begingroup$ 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 $\endgroup$ 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$
-
$\begingroup$ Thank you robjohn let me digest this. $\endgroup$ Feb 6, 2018 at 7:52