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?

 A: 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$.
A: $f(n)$ should never be greater than $n^3$, because it's the product of three positive numbers each of which is less than $n$.  But you don't need to prove that it's greater than $n^3$; just that it's greater than some multiple of $n^3$.  Rather than use your approach, I would suggest picking a value of $C$ and then choosing a $n_0$ to match.  The choice of $C=\frac18$ is particularly straightforward here; can you understand the circumstances under which $(n-1)(n-2)(n-3)$ must be greater than $\frac{n}2\cdot\frac{n}2\cdot\frac{n}2$?  (Hint: $n-1\gt n-3$ and $n-2\gt n-3$)  Once you can figure out when that holds, then you have your $n_0$ and your $C$ so you should be all set.
A: 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.)
