Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Thank you.

share|improve this question

closed as off-topic by Danny Cheuk, Dominic Michaelis, draks ..., Michael Albanese, Thomas Andrews Jul 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.

2  
What have you tried? –  Cameron Buie Jul 12 '13 at 16:22
    
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
add comment

4 Answers

up vote 5 down vote accepted

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)}$

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
I like your gravitar of the day! –  amWhy May 19 at 16:46
add comment

Note that,

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

In your case, we have

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

share|improve this answer
add comment

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$

share|improve this answer
add comment