growth rate of n! versus $r^n$

Question

How do you show that $\lim_{n\to \infty} {n!\over {r^n}} $ approaches $\infty$?

the growth rate of $r^n$ is slower than $n!$, so the latter one is increasing faster, but how do you show the above question using analytical computation?

Answer 1

Denote $A=\{n\in \mathbb{N}\mid \frac{n}{r}\geq 2\}$. $A$ is a set of integers bounded from below thus it has a minimum. Let $n_0=min_n\{n\in A\}$. Now we have $\frac{n!}{r^n}\geq \frac{n_0!}{r^{n_0}}2^{n-n_0}$. The inequality applies for the limits: $lim_{n\rightarrow \infty}\frac{n!}{r^n}\geq lim_{n\rightarrow \infty}\frac{n_0!}{r^{n_0}}2^{n-n_0}=\frac{n_0!}{(2r)^{n_0}}lim_{n\rightarrow \infty}2^{n}=\infty$.

Answer 2

Let $f(n)=r^n/n!$ As soon as $n\geq2 r$ we have $f(n+1)=r^{n+1}/(n+1)!=(r/(n+1))r^n/n!=(r/(n+1)f(n)<(1/2)f(n)$ so every time we increase n by 1, the value of $f(n)$ drops by more than half. E.g. for $n\geq 2 r$ we also have $n+1>2 r$ and $n+2> 2r$, so $f(n+3)<f(n+2)/2<f(n+1)/4<f(n)/8.$