<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] Your claim is that $n_0=7$ and $C=1$ work: that if $n>7$, then $f(n)\ge g(n)$, but you haven’t actually proved it. And you cannot possible prove it, because 
$$\frac{f(n)}{g(n)}=\frac{(n-1)(n-2)(n-3)}{n^3}=\frac{n-1}n\cdot\frac{n-2}n\cdot\frac{n-3}n<1^3=1\tag{1}$$
for all $n\ge 1$, and therefore $f(n)<g(n)$ for all $n\ge 1$.
You want to find $n_0$ and $C>0$ such that $f(n)\ge Cg(n)$ whenever $n>n_0$. Since $g(n)\ne 0$ when $n\ge 1$, this amounts to wanting a $C>0$ such that $\frac{f(n)}{g(n)}\ge C$ whenever $n>n_0$. In view of $(1)$, any such $C$ is going to have to be less than $1$, since $\frac{f(n)}{g(n)}$ is always less than $1$.
As you already computed, we do have
$$\frac{f(n)}{g(n)}=\frac{n^3-6n^2+11n-6}{n^3}=1-\frac6n+\frac{11}{n^2}-\frac6{n^3}\;.$$
Let’s find something smaller than this that is still positive, at least when $n$ is large enough. I’ll do it by progressively increasing the amount that I’m subtracting from $1$ on the righthand side, thereby making the difference smaller, and at the same time making the expression on the righthand side simpler:
$$\begin{align*}
\frac{f(n)}{g(n)}&=1-\frac6n+\frac{11}{n^2}-\frac6{n^3}\\\\
&>1-\frac6n-\frac{11}{n^2}-\frac6{n^3}\\\\
&>1-\frac{11}n-\frac{11}{n^2}-\frac{11}{n^3}\\\\
&=1-11\left(\frac1n+\frac1{n^2}+\frac1{n^3}\right)\\\\
&\ge1-11\left(\frac1n+\frac1n+\frac1n\right)\\\\
&=1-\frac{33}n
\end{align*}$$
whenever $n\ge 1$. And now I see that if $n\ge 34$, then
$$\frac{f(n)}{g(n)}\ge 1-\frac{33}{34}=\frac1{34}\;.$$
In other words, I’ve proved that if $n\ge 34$, then $f(n)\ge\frac1{34}g(n)$. This shows that $f(n)$ really is $O\big(g(n)\big)$.
(To answer the last question, $C$ can be any positive real number; it need not even be rational, let alone an integer.)
</s>