-1
$\begingroup$

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). $$

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

Here is the computer science approach to answering this question.

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)$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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