How do you prove that $\binom{n}{d} = \Theta(n^d)$?

Question

I am stuck on proving that that $\binom{n}{d} = \Theta(n^d)$ for any positive fixed integer d. I tried using the fact that if this is true, it means that for some integers c$_1$ and c$_2$, $c_1n^d \le |\frac{n!}{(n-d)!d!}| \le c_2n^d$ for any $n \ge n_0$ where $n_0$ is an integer. I tried using the fact that since n is greater than d and d is positive, then $|\frac{n!}{(n-d)!d!}|$ = $\frac{n!}{(n-d)!d!}$.

If the above equation is true in which the binomial expansion is bounded, then it would mean that $c_2 \ge \frac{n!}{n^d(n-d)!d!}$, and similarly, $c_1 \le \frac{n!}{n^d(n-d)!d!}$ So I have absolutely no idea how to find these constants $c_1$ and $c_2$, let alone find what $n_0$ is.

Can someone please help me with this in a way that allows me to at least understand more of what's going on here?

Thank you in advance.

Answer 1

Hint:

$$\binom n3=\frac{n^3-3n^2+2n}6=\Theta(n^3).$$

---

More hint:

Consider the function

$$\frac{\displaystyle\binom n3}{n^3}=\frac1{3!}\left(1-\frac0n\right)\left(1-\frac1n\right)\left(1-\frac2n\right).$$

For $n>2$, this is a growing function, as all factors are positive and growing. Then for $n\ge3$, its range is

$$\left[\frac1{27},\frac16\right].$$

More generally,

for $n\ge d, \dfrac1{d^d}\le\dfrac{\displaystyle\binom nd}{n^d}\le\dfrac1{d!}$.