Big $\Omega$ question! Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$

Question

Problem

Prove $(n-1)(n-2)(n-3)$ is $\Omega(n^3)$.

Attempt @ Solution

1. $f(n) = n^3(1-6/n+11/n^2-6/n^3)$
2. $g(n) = n^3$
3. Show that there exists a $C > 0$ and $n_0$ such that $f(n) \ge Cg(n)$ for all $n > n_0$.
4. 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?

Answer 1

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

Answer 2

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

Answer 3

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.)