How to evaluate $\lim_{n\to\infty}n!/n^{k}$

Question

I do not know how to go about finding the limit of this sequence. I know it diverges to infinity yet I can't find terms to use the squeeze lemma effectively.

$a_n = \frac{n!}{n^{1000}}$

$\lim_{n\rightarrow\infty} \frac{n!}{n^{1000}}$

I know that when $n>1000$, the numerator will "run out" of denominators and the expression will grow, yet I don't know how to formally prove this divergence.

In addition to this, since it is a sequence, no series laws can be applied.

Anyone have an idea on how to approach this type of problem?

Answer 1

I will first assume that $k$ is a positive integer. Observe that $$ \frac{n!}{n^k}=\frac{n}{n}\frac{n-1}{n}\cdots\frac{n-k+1}{n}(n-k)!\geq \Big(1-\frac{k-1}{n}\Big)^k(n-k)!\geq 2^{-k}(n-k)! $$ for all sufficiently large $n$. And $$ \lim_{n\to\infty}2^{-k}(n-k)!=\infty $$ for $k$ fixed, so the original sequence diverges as well.

If $k$ is a positive real number but not an integer, then if $j=\lceil k\rceil$ then $$\frac{n!}{n^k}\geq \frac{n!}{n^j}$$ so we can use the above argument.

Answer 2

This is probably overkill, but we can use Stirling's Approximation that

$$n! \sim \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$$

Then, we have

$$\lim_{n\to\infty} \sqrt{2\pi n} \frac{\left(\frac{n}{e}\right)^n}{n^k}$$

which certainly diverges to $\infty$ if

$$\lim_{n\to\infty} \frac{n^n}{e^nn^k}$$

does. This is equal to

$$\lim_{n\to\infty} \frac{n^{n-k}}{e^n}$$

and since the denominator is of a lower asymptotic order than the numerator (we can use the ratio test to get that $n$ increasing by $1$ increases the expression inside the limit by a factor of at least $\frac{n}{e}$), we get that this diverges, and the original must as well.

Answer 3

$$\log\frac{n!}{n^k} = \log n!-\log n^k = \sum_2^n \log i - k\log n$$

Let's apply the intergral test. Note that: $$\int_2^{n} \log x\; dx-k \log n = x\log x\Bigg|_{2}^{n} - k\log n$$

So, for $n>k$, we get:

$$x\log x\Bigg|_{2}^{n} - k\log n = (n-k)\log - 2\log 2 n>0$$

And

$$\lim_{n\to \infty} (n-k)\log n - 2\log 2 = \infty$$

Hence, the series diverges, which implies:

$$\forall k\lim_{n\to \infty}\frac{n!}{n^k} = \infty$$

Answer 4

Intuitively you know this must not converge because $n!$ requires $n$ multiplications whereas $n^k$ only involves $k$ multiplications. Clearly as $n$ grows, the numerator grows more rapidly than the denominator. The issue is that as $n$ grows both $n!$ gets bigger and $n^k$ gets bigger. What we need to do is get a lower bound on $n!$. All we need is $k$ terms in $n!$ that are bigger than $n$--but, of course, this isn't possible.

So instead of trying to get $k$ terms in $n!$ that are bigger than $n$, let's see what happens when you try to get $k$ terms that are bigger than a fraction of $n$. Really any fraction will do, but let's make it concrete and try $\frac{n}{2}$:

Find $n$ such that $n - \frac{n}{2} \geq k \rightarrow n \geq 2k$. Now if $n \geq 2k$ then we can say that $n! \geq \left(\frac{n}{2}\right)^k$. This is saying that if $n$ is greater than $\frac{n}{2}$ by more than $k$ terms then $n!$ is greater than the minimum, $\frac{n}{2}$, multiplied by $k$ times.

This starts to form a possible solution. We know that $n! \geq \left(\frac{n}{2}\right)^k$ therefore we can say that $\frac{n!}{n^k} \geq \left(\frac{1}{2}\right)^k$. This certainly suggests that this sequence diverges but doesn't prove it. The problem is in $\frac{n^k}{n^k}$. Instead of $n \geq 2k$ we can go ahead and add anything to that and sum, for instance, $\frac{n}{2}\geq k + 1 \rightarrow n \geq 2k+2$. In this case we get:

\begin{align} n! \geq \left(\frac{n}{2}\right)^{2k+2} \\ \frac{n!}{n^k} \geq&\ \frac{\left(\frac{n}{2}\right)^{2k+2}}{n^k} \\ \geq&\ \frac{n^{k + 2}}{2^k} \end{align}

Now clearly as $n$ goes towards infinity, this limit diverges.

This is a way to argue a squeeze theorem. You could generalize this argument to be any fraction rather than $\frac{1}{2}$.

Answer 5

In the same spirit as previous answers, considering $$a_n=\frac{n!}{n^k}\implies \log(a_n)=\log(n!)-k \log(n)$$ and using Stirling approximation $$\log(n!)=n (\log (n)-1)+\frac{1}{2} \left(\log (2 \pi )+\log \left({n}\right)\right)+O\left(\frac{1}{n}\right)$$ then $$\log(a_n)=n (\log (n)-1)-(k-\frac 12)\log(n)+\frac 12 \log(2\pi)+O\left(\frac{1}{n}\right)$$ Then, because of the first term, $\log(a_n)\to \infty$ and $a_n\to \infty$ for any value of $k$.