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

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?

• Hint: write $n!/(n-d)!$ as $n(n-1)(n-2)\cdots(n-d+1)$. – Greg Martin Apr 2 at 7:52

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!}$$.

• How does $\frac{n^3 - 3n^2 + 2n}{6} = \Theta(n^3)$ ? You can't factor out $n^3$ such that $\frac{n^3 - 3n^2 + 2n}{6} \le kn^3$ for some $k$. – Tim Apr 2 at 8:21
• @tim: of course I can ! Try with $k=1$. – Yves Daoust Apr 2 at 8:24
• Why did you write it out like $\frac{\binom{n}{3}}{n^3} = \frac{1}{3!}(1-\frac{0}{n})(1-\frac{1}{n})(1-\frac{2}{n})$? I just had $\frac{\binom{n}{3}}{n^3} = \frac{1}{3!}(1-\frac{3}{n}+\frac{2}{n^2})$ – Tim Apr 2 at 8:41
• @Tim: read my explanations. – Yves Daoust Apr 2 at 9:20
• Yes, I see what you mean now. Thank you. – Tim Apr 2 at 9:59