# How to find upper and lower bound without using formula

I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful.

Prove the following sum is $\Theta (n^2)$ (we have to find $O(n^2)$ and $\Omega (n^2)$)

1. $P(n)= 1+2+3+4\cdots + n$

2. $P(n) = n+(n+1)+(n+2)+\cdots +2n$

Note you cannot use any formula you have to do it my algebraic manipulation. This might be simple but I am not getting any clue right now and I dont have solution of it.

• Wikipedia shows you how to derive that the first sum is $\tfrac12n(n+1)$ and the second sum is the first sum plus $n^2$. – David Richerby Dec 15 '14 at 8:18

Another approach:

• $n^2/4=(n/2)^2= \underbrace{n/2 + n/2 +\cdots + n/2}_{n/2 \text{ times}} \le 1+2+\cdots + n \le \underbrace{n + n +\cdots + n}_{n \text{ times}} = n^2$

• $n^2= \underbrace{n + n +\cdots + n}_{n \text{ times}} \le n+(n+1)+\cdots + 2n \le \underbrace{2n + 2n +\cdots + 2n}_{n \text{ times}} = 2n^2$

Hint: For the first case of $P(n)$

1. Rewrite in reveresed order the right side of $P(n)$ to make another expression for $P(n)$.
2. Sum these expressions for $P(n)$
3. Solve the equation for $P(n)$. You should get it something like this. $$2 P(n) = n (n+1) \leq (n+1)^2 \in O(n^2)$$

$$2 P(n) = n (n+1) \geq n^2 \in \Omega(n^2)$$

Then, $P(n)\in \Theta(n^2)$.

For the second case, you could do the same thing that in the previous one, it just difference by $n$ so factorize it.

• you can add that this is gauss trick and may give some historical importance. – Phani Raj Feb 10 '15 at 13:14

Clue: You only need to prove it, instead of finding it out. Mathematical induction is for this. IMO, this is what the problem wants you to do.