3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Tim Apr 2 at 8:21
  • $\begingroup$ @tim: of course I can ! Try with $k=1$. $\endgroup$ – Yves Daoust Apr 2 at 8:24
  • $\begingroup$ 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})$ $\endgroup$ – Tim Apr 2 at 8:41
  • $\begingroup$ @Tim: read my explanations. $\endgroup$ – Yves Daoust Apr 2 at 9:20
  • $\begingroup$ Yes, I see what you mean now. Thank you. $\endgroup$ – Tim Apr 2 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.