4
$\begingroup$

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!

$\endgroup$
  • 2
    $\begingroup$ since $\lim_\limits{n\to\infty} \frac{x_{n+1}}{x_n}=\frac1{e}<1$, the given limit is zero. $\endgroup$ – farruhota Jan 7 at 15:48
  • $\begingroup$ @farruhota oh my, how have i missed that. Thank you! $\endgroup$ – roman Jan 7 at 15:55
3
$\begingroup$

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 $$

$\endgroup$
1
$\begingroup$

I think your second approach is bigger. Starting from where you left off, as $n$ increases, you know $n\gg k$. Then rewrite $x_n$ as $$e^k\frac{n!}{n^{n-k}}$$

Ignoring the coefficient of $e^k$ for now, you can compare the numerator and denominator term-by-term using the definition of factorial and exponentiation, and the next steps to take should be more clear. I can edit if you need more of a nudge.

$\endgroup$
1
$\begingroup$

As you got $\frac{(n+k)!}{n^n}\leq \frac{n!}{n^{n-k}}\left(1+\frac k n\right)^k.$ Now $\left(1+\frac k n\right)^k\rightarrow 1$ as $n\rightarrow \infty$ for a fixed $k\in\mathbb{N}$ and $\frac{n!}{n^{n-k}}=k!\frac{(k+1)(k+2)\ldots n}{n^{n-k}}\leq k!\frac{(k+1)(k+2)\ldots \left\lfloor \frac n 2\right\rfloor}{n^{\left\lfloor \frac n 2\right\rfloor-k}}\leq k!\left(\frac12\right)^{\left\lfloor \frac n 2\right\rfloor-k}\rightarrow 0$ as $n\rightarrow \infty$ for a fixed $k\in\mathbb{N}.$ So, $\frac{(n+k)!}{n^n}\rightarrow 0.$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.