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

I have left with some functions I can't find witenesses for proving/disproving Big Ω equalities relations.

Here are the three relations:

  1. $ \sum\limits_{i=1}^{n} (i^3 - i ^2) = \Omega(n^4) $
  2. $log(n-\sqrt{n}) = \Omega(logn)$
  3. $log(n+\sqrt{n}) = \Omega(logn)$

For the first one I tried to split the sum but to no avail. The second and the third - I don't even have an idea how to start proving/disproving this equality..

Thank you very much !

share|cite|improve this question
For the first one there are known formulas for $\sum i^3$ and for $\sum i^2$ where $i=1..n$. Namely $[n(n+1)/2]^3$ and $n(n+1)(2n+1)/6$ respectively. This may help; I don't know what $\Omega(n^4)$ means, just not up on the notation. – coffeemath Feb 8 '13 at 13:46
For the 2nd and 3rd, L'hopital it. For the first, as coffeemath said use the formulae. Integral approximation is also fine. – Ishan Banerjee Feb 8 '13 at 14:59
up vote 1 down vote accepted

$$ S_1 = \sum_{k=1}^{n}(k^3-k^2)\geq \frac{n^4}{4}-\frac{n^3}{3} = \Omega (n^4) $$

The $\geq$ is due to comparison with the integral. $$ S_2=\log (n-\sqrt{n})=\log (\sqrt{n}(\sqrt{n}-1))\geq \frac{1}{2}\log n + \frac{1}{2} \log n - \log 2 \geq \log n -\log 2 = \Omega(\log n) $$ The first $\geq$ is due to $\log (\sqrt{n}-1) \geq \log \big( \frac{\sqrt{n}}{2} \big) $

can you handle the third one from here?

share|cite|improve this answer
This is very good explanation. Thank you very much – SyndicatorBBB Feb 8 '13 at 18:49
You are welcome – Alex Feb 8 '13 at 18:51

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.