<s>[INST] Big $\Omega$ question! Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$ Problem
Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$.
Attempt @ Solution


*

*$f(n) = n^3(1-6/n+11/n^2-6/n^3)$

*$g(n) = n^3$

*Show that there exists a $C > 0$ and $n_0$ such that $f(n) \ge Cg(n)$ for all $n > n_0$.

*I tried plugging in different numbers for $n$ that would make $f(n) > n^3$.  I found that setting $n = 7$ makes sure that $f(n)$ is greater than $g(n)$.  So, is that my answer?  Evaluating the expression with $n=7$ to solve for $C$, and setting $n_0$ as $7$?  Is that a sufficient proof?  Also, Does my constant have to be a Natural number, or can it simply be a Rational number?

 [/INST] You will not be able to show that $f(n)\gt g(n)$, because it is in fact smaller.
What I would suggest is that if $n\ge 6$, then $n-3\ge \frac{n}{2}$, as are $n-2$ and $n-1$. Thus for $n\ge 6$, we have $f(n)\ge \frac{1}{8}g(n)$.  So we can take $C=\frac{1}{8}$.
And $C$ certainly does not have to be an integer. In our particular problem, we cannot even find a positive  integer $C$ with the desired property. 
Remark: Dividing by $n^3$ like you did was a good idea, expanding was not. When we divide by $n^3$ we get
$$\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\left(1-\frac{3}{n}\right).$$
Now you can take your favourite $n\ge 4$. Let's pick $6$. Then if $n\ge 6$, the above expression is $\ge \frac{5}{6}\cdot \frac{4}{6}\cdot \frac{3}{6}$. We can pick this for our $C$.
</s>