# Prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$. (Big-o notation) [closed]

Will someone help me prove that $(n+1)(n+2)(n+3)$ is $O(n^3)$?

Thank you.

-

## closed as off-topic by Danny Cheuk, Dominic Michaelis, draks ..., Michael Albanese, Thomas AndrewsJul 24 '13 at 6:29

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Homework questions must seek to understand the concepts being taught, not just demand a solution. For help writing a good homework question, see: How to ask a homework question?." – Community, Dominic Michaelis, draks ..., Michael Albanese, Thomas Andrews
If this question can be reworded to fit the rules in the help center, please edit the question.

Did you get no inspiration from the answers to your multiple previous questions on the subject, to approach this one? – Did Jul 13 '13 at 11:22

Hint: For all positive integers $n$, your expression is $\le (n+n)(n+2n)(n+3n)$.

Remark: A fancier way of doing the same thing is to show that $$\frac{(n+1)(n+2)(n+3)}{n^3}$$ is bounded above, that is, that there is a constant $C$ such that $\frac{(n+1)(n+2)(n+3)}{n^3}<C$. With some algebra, we find that
$$\frac{(n+1)(n+2)(n+3)}{n^3}=\left(1+\frac{1}{n}\right)\left(1+\frac{2}{n}\right) \left(1+\frac{3}{n}\right).$$ Each term on the right is less than $5$ (we are giving away a lot), so we can take $C=5^3$.

The reason for the fancier approach is that to show that $f(n)=O(g(n))$ it is often useful to concentrate on the ratio $\dfrac{f(n)}{g(n)}$

-
How did you come to this conclusion? – user84059 Jul 12 '13 at 16:34
The third term for exmple was $n+3$. But $3\le 3n$ for all positive integers $n$. Same with the others. The idea is to make upper estimates that yield simpler expressions. Constants don't matter in the $O(f)$ game. – André Nicolas Jul 12 '13 at 17:03

We have $$(n+1)(n+2)(n+3)\leq (n+3)^3\leq (n+3n)^3=4^3n^3$$ and the other inequality is immediate and you conclude.

-
I like your gravitar of the day! – amWhy May 19 '14 at 16:46

Note that,

if $\lim_{n\to \infty} \frac{f(n)}{g(n)}=c$, $c$ is finite, then $f=O(g)$.

$$\lim_{n\to \infty} \frac{(n+1)(n+2)(n+3)}{n^3}=1,$$
which implies $(n+1)(n+2)(n+3)=O(n^3) .$
The easiest I guess: $$(n+1)(n+2)(n+3)\leq(n+3)^3 \leq 4n^3=O(n^3)$$ The second inequality is for $n>N$, appropriately selected $N$