In what circumstance do we have $k \geq \frac{{n \choose 6}}{{n \choose 3}}$ implies $k \geq n^3$?

29 Views Asked by At

In one of my lectures we derive the inequality $k \geq \frac{{n \choose 6}}{{n \choose 3}}$, where $k$ is a variable and $n$ the number of vertices in a graph. The lecturer then proceeds to state that "for $n$ large enough, we have $k \geq n^3$". I can see that $\frac{{n \choose 6}}{{n \choose 3}} = \frac{(n-3)(n-4)(n-5)}{6\cdot 5\cdot 4}$, and as $n$ grows large, $n^3 \approx (n-3)(n-4)(n-5)$. But the RHS never grows bigger than the LHS. So how can we make that claim about $k$?

1

There are 1 best solutions below

2
On BEST ANSWER

You can't. What you can say, and what the lecturer probably meant, is that for $n$ large enough we have $k\geq cn^3$ where $c>0$ is some absolute constant. Presumably this is good enough for whatever you actually use the bound to prove.