<s>[INST] Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$ Problem


*

*Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$



Attempt at Solution


*

*$f(n) = (n+1)(n+2)(n+3)$

*$g(n) = n^3$

*Show that there exists an $n_0$ and $C > 0$ such that $f(n) \le Cg(n)$ whenever $n > n_0$

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

*$f(n) \le C*g(n)$ is

*$n^3(1 + 6/n + 11/n^2 + 6/n^3) \le C*n^3$ is

*$(1 + 6/n + 11/n^2 + 6/n^3) < C$

That's as far as I got.  Should I plug in a value for n to find C?  And then, would that value I plugged in for n be $n_0$?
Any help is appreciated.
Thank you in advance.
 [/INST] Your multiplication isn't quite correct. You should get
$$(n + 1)(n + 2)(n + 3) = (n + 1)(n^2 + 5n + 6) = n^3 + 6n^2 + 11n + 6$$
Now proceeding as you did, we get
$$f(n) = n^3 (1 + \frac{6}{n} + \frac{11}{n} + \frac{6}{n^3})$$
Note that if $n \geq 1$, then $1/n \leq 1$; likewise, $1/n^2 \leq 1$ and $1/n^3 \leq 1$. Hence, try choosing 
$$C = 1 + 6 + 11 + 6$$
</s>