Proving $\Theta(n^{k})= {n \choose k}$

Question

I need help proving $n\choose k$$=\Theta(n^{k})$ where $f(n)=\Theta(g(n))$

if $0<\liminf\limits_{n\rightarrow\infty}\frac{g(n)}{f(n)}\le\limsup\limits_{n\rightarrow\infty}\frac{g(n)}{f(n)}<\infty$

Can someone show me the calculation?

Answer 1

$$ {n\choose k}=\frac{n!}{k!(n-k)!}= \frac{n(n-1)\ldots(n-k+1)}{k!} $$

Notice that the right hand side has $k$ terms in the numerator, and each of those is less than $n$. So $$ {n\choose k}\leq \frac{n^k}{k!} $$

Therefore we have $\limsup_{n\to\infty}{n\choose k}/n^k\leq \frac{1}{k!}$.

For the other side we need a lower bound.

In the first equation each term in the numerator on the right hand side is at least $n-k+1$. So

$$ {n\choose k}\geq \frac{(n-k+1)^k}{k!} $$

Therefore we have $$ \liminf_{n\to\infty}{n\choose k}/n^k\geq \frac{1}{k!}\liminf_{n\to\infty}\frac{(n-k+1)^k}{n^k}. $$

But actually the $\liminf$ on the right is a well-defined limit:

$$ \lim_{n\to\infty}\frac{(n-k+1)^k}{n^k}=1. $$

This can be seen using L'Hopital's Rule for example.

Putting everything together:

$$ \frac{1}{k!}\leq\liminf_{n\to\infty}{n\choose k}/n^k\leq\limsup_{n\to\infty}{n\choose k}/n^k\leq \frac{1}{k!}. $$

So actually: $$ \lim_{n\to\infty}{n\choose k}/n^k=\frac{1}{k!} $$

But the