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 need to learn how to prove/disprove each of the following. Anyone able to do it in very simple way for a NON -mathematician to easily understand? ( NB -- NOT HOMEWORK)

a) $$n^2 + n + 1 = \Theta (n^2)$$ b) $$ n^2 = \omega(2^n)$$ c) $$n^2 = o (2^n)$$ d) $$\left|n \sin {\pi\cdot n\over 2}\right| = \Theta(n)$$

share|cite|improve this question
up vote 2 down vote accepted

For all sufficiently large $n$, $n^2 < n^2 + n + 1 < 2n^2$. Hence 1) is true.

For any positive $k$, $n^2 < k2^n$ for all sufficiently large $n$. Hence 2) is not true (whether with $\omega$ or $\Omega$).

Given any $\varepsilon > 0$, $0 < n^2/2^n < \varepsilon$ for all sufficiently large $n$. Hence 3) is true.

Finally, 4) is not true, since $n\sin (\pi n/2) = 0$ for infinitely many (positive integers) $n$.

share|cite|improve this answer
Where did you get 2 from? $n$, $n^2 < n^2 + n + 1 < 2n^2$. – user10695 Jul 11 '11 at 21:50
@user10695: We want to show that there exist positive constants $k_1$ and $k_2$ such that $k_1 n^2 \leq n^2 + n + 1 \leq k_2 n^2$ for all sufficiently large $n$. This obviously holds with $k_1 = 1$, and it is easy to see that this holds with $k_2 = 2$, noting that $n+1 < n^2$ for all sufficiently large $n$ (actually, for all $n \geq 2$). – Shai Covo Jul 11 '11 at 22:03
oooh!! I see it now! thanks – user10695 Jul 11 '11 at 22:56

(n.b.: for all definitions I'm taking the Wikipedia version as gospel)

For (a): you need to show that there are constants $k_1$ and $k_2$ such that $k_1\cdot n^2 \leq n^2+n+1 \leq k_2\cdot n^2$ for all sufficiently large $n$ - or in other words, dividing through by $n^2$, constants $k_1$ and $k_2$ such that $k_1 \leq 1+{1\over n}+{1\over n^2} \leq k_2$ for all sufficiently large $n$. Try plugging in some values of $n$ and you should be able to make a reasonable hypothesis about the behavior of the term in the middle; this will give you your bounds.

The others follow rather similarly - except for (d), which by the Wikipedia definition is actually false as written. Hint: what are the values on the left hand side? Can you show that there is no positive $k_1$ such that $\left|n\sin(\pi\cdot n/2)\right|\geq k_1n$ for all sufficiently large $n$?

share|cite|improve this answer

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.