Evaluate the limit:
$$
\lim_{n\to\infty}\frac{(n+k)!}{n^n}, \ n,k\in\Bbb N
$$
I would like to avoid Stirling's approximation, derivatives and Cesaro-Stolz, since none of them has been yet introduced.
I've tried to apply the old ratio test in order to show the sequence is bounded and monotone, hence convergent, but that leads to nowhere. At least I couldn't find the appropriate bounds:
$$
\frac{x_{n+1}}{x_n} = \frac{(n+k+1)!}{(n+1)^{n+1}} \cdot \frac{n^n}{(n+k)!} \\
=\frac{n+k+1}{n+1}\cdot \frac{n^n}{(n+1)^n} \\
=\underbrace{\left(1+{k\over n+1}\right)}_{>1}\underbrace{\frac{n^n}{(n+1)^n}}_{<1}
$$
This is not conclusive at all. Some further thoughts are:
$$
\begin{align}
x_n &= \frac{n!}{n^{n-k}}\cdot \frac{n+1}{n}\cdot \frac{n+2}{n} \cdots\cdot \frac{n+k}{n} \\
&= \frac{n!}{n^{n-k}} \left(1+{1\over n}\right)\left(1+{2\over n}\right)\cdots\left(1+{k\over n}\right) \\
&\le \frac{n!}{n^{n-k}} \left(1+{k\over n}\right)^k \\
&\le \frac{e^kn!}{n^{n-k}}
\end{align}
$$
Not sure how to squeeze it though. I know the limit is $0$ since $x_n$ is decreasing starting from some $N$ towards $0$. But how do I rigorously show that? I would prefer a hint rather than a full answer. Thank you!
Best Answer
Apply the ratio test to the series $$ \sum_{n=0}^{\infty}\frac{(k+n)!}{n^n} $$ The ratios to evaluate are $$ \frac{(k+n+1)!}{(n+1)^{n+1}}\frac{n^n}{(k+n)!}=\frac{k+n+1}{n+1}\frac{n^n}{(n+1)^n} $$ Note that the limit of the first fraction is $1$ and the limit of the second fraction is $1/e<1$.
By the ratio test, the series is convergent. Hence $$ \lim_{n\to\infty}\frac{(k+n)!}{n^n}=0 $$