# Is $\sum_{i=1}^n i \in \Theta(n^2)$?

Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing.

$$\sum_{i=1}^n i \in \Theta(n^2).$$

• There is a formula for $\sum_{i=1}^n i$. Apply the formula, and see what you get. – Yuval Filmus Feb 26 '19 at 16:19
• I have done it and got to a conclusion which most likely disproves. – Physics Feb 26 '19 at 16:22
• What is your argument? – Yuval Filmus Feb 26 '19 at 16:23

On the one hand, we have $$\sum_{i=1}^n i \leq \sum_{i=1}^n n = n^2.$$ On the other hand, we have $$\sum_{i=1}^n i \geq \sum_{i=\lfloor n/2 \rfloor}^n \lfloor n/2 \rfloor = \lfloor n/2 \rfloor \lceil n/2 \rceil \geq (n/2)^2 - 1/4,$$ since when $$n$$ is odd, $$\lfloor n/2 \rfloor \lceil n/2 \rceil = (n/2-1/2)(n/2+1/2)$$.