Approximation of combination $ {n \choose k} = \Theta \left( n^k \right) $?

Is it a valid to say $$ {n \choose k} = \Theta \left( n^k \right) $$ for any $n$ and $k$? If so, how to prove it?

Note: $k$ is not a function of $n$.

Note: Observed it here (page 5): http://www.cs.berkeley.edu/~sinclair/cs271/n6.pdf

enter image description here


You have that $$ \binom{n}{k} = \frac{n!}{(n-k)!k!} = \frac{1}{k!}\frac{n!}{(n-k)!} = \frac{1}{k!}\left(n(n-1)(n-2)\dots(n-k+1)\right). $$ As far as the $\Theta(\cdot)$ notation is concerned, $k$ is a constant, so $\frac{1}{k!}=\Theta(1)$, and $$ \left(n(n-1)(n-2)\dots(n-k+1)\right) = n^k\cdot\left(1\left(1-\frac1n\right)\left(1-\frac2n\right)\dots\left(1-\frac kn\right)\right) $$ and as $k$ is fixed,, $$ \left(1\left(1-\frac1n\right)\left(1-\frac2n\right)\dots\left(1-\frac kn\right)\right) \xrightarrow[n\to\infty]{} 1 $$ so that indeed $$ \binom{n}{k} = \Theta(n^k) $$


We can even make a stronger statement that $${n \choose k} = O\left (\left( \frac{e \cdot n}{k} \right)^k \right)$$ For the proof, see this.