Limit of $(n-k)! \cdot n^k$ as $n$ approaches infinity

Question

Is it true that $(n-k)! \cdot n^k$ tends to $n!$ as $n \to \infty$?

I think it is correct but can't think of a satisfying proof.

Answer 1

Hint: Notice that $$\frac{n^k \cdot (n-k)!}{n!} = \frac{n}{n-k+1} \cdot \frac{n}{n-k+2} \cdots \frac{n}{n-k+k}$$ and $$1 \leq \frac{n}{n-k+j} \leq \frac{n}{n-k+1}=1+ \frac{k-1}{n-k+1}$$ for all $1 \leq j \leq k$.

[I assumed the question actually asks to show that $\frac{n^k \cdot (n-k)!}{n!} \to 1$ as suggested by user127.0.0.1.]

Answer 2

By the Stirling approximation $$n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}$$ If you use this, you obtain that $$\lim_{n \rightarrow + \infty}\frac{(n-k)! \cdot n^{k}}{n!} = 1$$

Answer 3

Sterling's approximation says $\ln (x!) = x \ln x - x + \frac12\ln(2\pi x) + O(\frac1x)$.

$$\ln \left((n - k)! n^k\right) = k \ln n + \ln \left((n - k)!\right)$$

$$ = k \ln n + (n - k)\ln(n - k) - (n - k) + \frac12 \ln (2 \pi (n - k)) + O(\frac1{n-k})$$

Since $\ln (n - k) = \ln\left(n(1 - \frac{k}n)\right) = \ln n + \ln (1 - \frac{k}n)$

$$ = k \ln n + (n - k)(\ln n + \ln(1 - \frac{k}n)) - n + k + \frac12 \ln (2 \pi (n - k)) + O(\frac1{n-k})$$

$$ = k \ln n + n \ln n - k \ln n + (n - k)\ln(1 - \frac{k}n) - n + k + \frac12 \left(\ln (2 \pi) + \ln n + \ln(1 - \frac{k}n)\right) + O(\frac1{n-k})$$

$$ = n \ln n + (n - k + \frac12)\ln(1 - \frac{k}n) + - n + k \frac12 \left(\ln (2 \pi) + \ln n \right) + O(\frac1{n-k})$$ Since for $x \ll 1$ we have $\ln(1 - x) = -x - O(x^2)$

$$ = n \ln n + (n - k + \frac12)\left(-\frac{k}n - O(\frac{k^2}{n^2})\right) - n + k \frac12\ln(2\pi n) + O(\frac1{n-k})$$

$$ = n \ln n - k + \frac{k^2}n - \frac{k}{2n} - O(\frac{k^2}{n})- n + k +\frac12\ln(2\pi n) + O(\frac1{n-k})$$

$$ = n \ln n - n + \frac12\ln(2\pi n) + O(\frac{k^2}n) $$

$$ = \ln(n!) + O(\frac1n) + O(\frac{k^2}n) = \ln(n!) + O(\frac{k^2}n)$$

So $(n - k)!n^k$ is approximately equal to $n!$ within a factor of about $e^{\frac{k^2}n}$. If you add in more terms of Sterling's approximation you might get a better big-O term.

Answer 4

For the lower bound note that $$ \frac{n!}{(n-k)!}=(n-k+1)(n-k+2) \cdots n =n(1-\frac{k-1}{n})\cdot n\cdot(1-\frac{k-2}{n})\cdot n\cdots n\\ =n^k(1-\frac{k-1}{n})(1-\frac{k-2}{n}) \cdots 1 \leq n^k$$ Hence $$\frac{(n-k)!n^k}{n!}\geq \frac{(n-k)!n!}{n!(n-k)!}=1 $$ for the upper bound use the same idea, i.e. $\frac{(n-k)!}{n!} \geq n^{-k}$. Hence $$ (n-k)!n^k=O(n!) $$

Answer 5

It depends in what context you intend that limit.

Using the identity $$ \frac{(n-k)!n^k}{n!}=\frac{n}{n}\frac{n}{n-1}\frac{n}{n-2}\cdots\frac{n}{n-k+1} $$ we get that $$ \color{#C00000}{\lim_{n\to\infty}\frac{(n-k)!n^k}{n!}=1} $$ However, the same identity shows that for $k\gt1$, $$ \frac{(n-k)!n^k}{n!}\ge\frac{n}{n-1}\gt1+\frac1n $$ and multiplying both sides by $n!$ and subtracting $n!$ yields $$ (n-k)!n^k-n!\gt(n-1)! $$ Therefore, for $k\gt1$, $$ \color{#C00000}{\lim_{n\to\infty}(n-k)!n^k-n!=\infty} $$