Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

Thank you.

share|cite|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.

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
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|cite|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

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|cite|improve this answer
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) $.

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|cite|improve this answer

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|cite|improve this answer