How to prove that $\lim\limits_{n \to \infty} \frac{k^n}{n!} = 0$

Question

It recently came to my mind, how to prove that the factorial grows faster than the exponential, or that the linear grows faster than the logarithmic, etc...

I thought about writing: $$ a(n) = \frac{k^n}{n!} = \frac{ k \times k \times \dots \times k}{1\times 2\times\dots\times n} = \frac k1 \times \frac k2 \times \dots \times \frac kn = \frac k1 \times \frac k2 \times \dots \times \frac kk \times \frac k{k+1} \times \dots \times \frac kn $$ It's obvious that after k/k, every factor is smaller than 1, and by increasing n, k/n gets closer to 0, like if we had $\lim_{n \to \infty} (k/n) = 0$, for any constant $k$.

But, I think this is not a clear proof... so any hint is accepted. Thank you for consideration.

Answer 1

If you know that this limit exists, you have $$ \lim_{n \to \infty} \frac{k^n}{n!} = \lim_{n \to \infty} \frac{k^{n+1}}{(n+1)!} = \lim_{n \to \infty} \frac k{n+1} \frac{k^n}{n!} = \left(\lim_{n \to \infty} \frac k{n+1} \right) \left( \lim_{n \to \infty} \frac {k^n}{n!} \right) = 0. $$ Can you think of a short way to show the limit exists? (You need existence to justify my factoring of the limits at the end. If you don't have that then there's no reason for equality to hold.)

Answer 2

Here is another observation. Fix $k$. Since you are trying to find the limit as $n\to \infty$ you may assume that $n > k$. Then you have

$$ \frac{k^n}{n!} = \frac k1 \cdot \frac k2 \cdots \cdot \frac kk \cdot \frac k{k+1} \cdots \frac kn = c \frac k{k+1} \cdots \frac kn$$

where $c = k^k/k!$ is a constant independent of $n$. Next, for $1\leq i \leq n-k$ we have

$$\frac{k}{k+i} \leq \frac{k}{k+1}.$$

Therefore

$$c \frac k{k+1} \frac k{k+2} \cdots \frac kn \leq c \underbrace{\frac k{k+1} \frac{k}{k+1}\cdots \frac{k}{k+1}}_{n-k \text{ times}} = \left(\frac{k}{k+1}\right)^{n-k}.$$

What would you try next?

Answer 3

The series for $e^k$ $$ \sum_{n=0}^\infty\frac{k^n}{n!} $$ converges by the ratio test. The terms of a convergent series must tend to $0$.

---

For $n\ge2k$, the ratio of terms is $\frac{k^{n+1}/(n+1)!}{k^n/n!}=\frac{k}{n+1}<\frac{1}{2}$. We can remove the reference to series (which seems to have bothered someone) with the following sandwich, valid for $n\ge2k$: $$ 0\le\frac{k^n}{n!}\le\frac{k^{2k}}{(2k)!}\left(\frac{1}{2}\right)^{n-2k} $$ which shows that $\displaystyle\lim_{n\to\infty}\frac{k^n}{n!}=0$.

Answer 4

Probably not the kind of solution you're looking for, but just for fun:

It's easy to show that $\frac{n!^{1/n}}{n} \to e^{-1}$ as $n \to \infty$. (For example, write $\int_0^1 \log t\: dt$ as a limit of Riemann sums on the partitions $0,1/n,2/n, \dots, 1))$.

Thus, by the root test,

$$\sum_{n=0}^\infty \frac{k^n}{n!}$$

converges. Hence $\lim_{n \to \infty} \frac{k^n}{n!} = 0$.

Answer 5

Of course, one can break out the ratio test to show that the series $\sum\limits_{n=1}^\infty \frac{k^n}{n!}$ converges (absolutely) and hence $\lim\limits_{n\rightarrow\infty}\frac{k^n}{n!}=0$.

However, we don't have to use nuclear weapons. Clearly, $a_n=\frac{k^n}{n!}$ is bounded below by zero. If $n\geq k$ (or, if $k$ isn't an integer, $n\geq \lceil k \rceil$), we have

$a_{n+1}=\frac{k^{n+1}}{(n+1)!}=\frac{k^n}{n!}\frac{k}{n+1}<\frac{k^n}{n!}=a_n$.

So, since the sequence $\{a_n\}$ is eventually decreasing and bounded below, it converges.

To show that it converges to zero, you can now use Patrick Da Silva's method above.

Answer 6

Your proof is clear to me. $k$ is fixed, so the right hand side of your equation, for $n>k$, has the form $$ {k\over n}\cdot\underbrace{{k\over n-1}\cdot{k\over n-2}\cdots{k\over k}}_{<1}\cdot C< {k \over n}\cdot C\rightarrow 0 $$

Answer 7

Let's observe an example :

$$\frac{9^n}{n!}$$ so we have that :

$$\frac{9^1}{1!}=9 , \frac{9^2}{2!}=40.5 , \frac{9^3}{3!}=121.5$$

but...

$$\frac{9^9}{9!}=\frac{9^8\cdot 9}{8! \cdot 9}=\frac{9^8}{8!}$$

and further...

$$\frac{9^{10}}{10!}=\frac{9^9\cdot 9}{9! \cdot 10} < \frac{9^9}{9!}$$

So we may conclude: after we throw out the first $k-1$ elements that sequence starts to decrease , therefore sequence :

$$\frac{k^n}{n!}$$

is decreasing if we set $ n\geq k$ , so we may conclude that :

$$n \rightarrow \infty \Rightarrow \frac{k^n}{n!} \rightarrow 0$$

Answer 8

As @robjohn has mentioned, this question is indeed very similar to Prove that $\lim \limits_{n \to \infty} \frac{x^n}{n!} = 0$, $x \in \Bbb R$. the only question is who to play the role of $7$ in our case ($7$ is the smallest number for which $7!>(2+1)^7$ ). The general proof is the following: let us prove first that for any $j\in\mathbb N$ it holds that $n!\geq j^n$ for all $n$ large enough.

1. First, let us put $N = j^2+j$, then $$ \frac{N!}{j^N} = \underbrace{\frac1j\cdot\frac2j\cdot\dots\cdot\frac jj}_{\pi_1}\cdot\underbrace{\frac{j+1}{j}\cdot\dots\cdot\frac{j^2}j}_{\pi_2}\cdot\underbrace{\frac{j^2+1}{j}\cdot\dots\cdot\frac{j^2+j}j}_{\pi_3}. $$ Now, $\pi_2\geq 1$ since all terms in the product are grater than $1$. Moreover, by multiplying correspondent terms $$ \pi_1\pi_3 = \frac{j^2+1}{j^2}\cdot\frac{2(j^2+2)}{j^2}\cdot\dots\cdot\frac{j(j^2+j)}{j^2}\geq1 $$ hence $N!\geq j^N$.

2. For all $n\geq N$ it clearly holds now that $n!\geq j^n$. By induction: it holds for $n=N$. If it holds for some $n$ then $$ (n+1)!\geq n!\cdot n\geq j^n\cdot n\geq j^{n+1} $$ since $n\geq N\geq j$.

We proved that for any $j\in\mathbb N$ there is $N(j)$ s.t. $n\geq N(j)\Rightarrow n!\geq j^n$. Now let us put $j=[k]+1$, then $$ 0\leq\lim\limits_{n\to\infty}\frac{k^n}{n!}\leq \lim\limits_{n\to\infty}\left(\frac k{[k]+1}\right)^n = 0. $$