Missing steps: Show the sum of the first n positive integers is of order $n^2$

Question

In Rowsen's Discrete Mathematics text, 6th edition. He has this problem as an example (#11) on page 190. His solution for obtaining a lower bound is to ignore the first half of the terms. He does the following:

\begin{align} &1:&1 + 2 + 3 ... + n &>= [n/2] + ([n/2] + 1) + ... + n \\ &2:&&>= [n/2] + [n/2] + ... + [n/2] \\ &3:&&\space\space\space= (n - [n/2] + 1)[n/2] \\ &4:&&>= (n/2)(n/2) \\ &5:&&\space\space\space= n^2/4 \\ \end{align}

So the answer is $\Theta(n^2)$. That I get, but how does one arrive to the simplification in line 2 and 4 (these appear similar to me, seems it includes as dropping the one for some reason). Also how is line 3 obtained? The algebra evades me here.

Answer 1

It might be easier to think of the problem visually and separately for even $n\;(=2m)$ and odd $n\;(=2m+1)$. In both cases, $m=[n/2]$ and also, for even $n$, $m=n/2$.

(1) $n=2m$ (even):

$$\begin{align} 1+2+3+\qquad\cdots\qquad +&[n/2]+([n/2]+1)+\quad\cdots\quad +n\\\\ =1+2+3+\cdots+(m-1)+ &m+(m+1)+(m+2)+\cdots+2m\\\\ >= &m+(m+1)+(m+2)+\cdots+2m&&\cdots(1)\\ >= &\overbrace{m+m+\qquad m+\qquad \cdots+m}^{2m-m+1\text{ of them}}&&\cdots(2)\\\\ = &(2m-m+1)\cdot m=\color{lightgray}{(m+1)\cdot m}&&\cdots(3)\\\\ >=&\left(\frac n2\right)\left(\frac n2\right)&&\cdots(4)\\\\ =&\frac{n^2}4&&\cdots(5) \end{align}$$

Note: $(3)=(m+1)m=(\frac n2+1)(\frac n2)\ge (\frac n2)^2=(4)$

(2) $n=2m+1$ (odd):

$$\begin{align} 1+2+3+\qquad\cdots\qquad +&[n/2]+([n/2]+1)+\quad\cdots\quad \qquad+n\\\\ =1+2+3+\cdots+(m-1)+ &m+(m+1)+(m+2)+\cdots+2m+(2m+1)\\\\ >= &m+(m+1)+(m+2)+\cdots+2m+(2m+1)&&\cdots(1)\\ >= &\overbrace{m+m+\qquad m+\qquad \;\cdots+m+\quad+m}^{(2m+1)-m+1\text{ of them}}&&\cdots(2)\\\\ = &((2m+1)-m+1)\cdot m=\color{lightgray}{(m+2)\cdot m}&&\cdots(3)\\\\ >=&\left(\frac n2\right)\left(\frac n2\right)&&\cdots(4)\\\\ =&\frac{n^2}4&&\cdots(5)\ \end{align}$$

Note: $(3)=(m+2)\cdot m=(\frac {n-1}2+2)(\frac{n-1}2)=\frac{(n+3)(n-1)}4=\frac{n^2+2n-3}4>\frac{n^2}4=(\frac n2)^2=(4)$

Answer 2

Line 2: each term in the top "half" is greater than or equal to $[n/2]$ so can be replaced by that all the way through.

Going to Line 3: The number of terms in the upper "half" is found by finding the difference and adding 1. Suppose the top half terms were the 4th, 5th, 6th, 7th, 8th and 9th terms. That is 6 terms. $9-4=5$ terms is the wrong calculation, so we need $9-4+1=6$ terms.

Going to Line 4: The number of terms will be $\frac n2$ if $n$ is even and $\frac n2 +1$ if $n$ is odd. The lower bound is $\frac n2$.

Answer 3

Line $2$ is obtained by saying that $[n/2]+k\geq [n/2]$, $\forall k\geq 1$ and by summing these inequalities.

Lines $3$ is obtained by counting the number of termes in line $2$.

For line 4, two cases:

• if $n$ is even, then $[n/2]=n/2$ and line $3$ is $(n-n/2+1)(n/2)=(n/2+1)(n/2)\geq (n/2)(n/2)$.
• if $n$ is odd, then $[n/2]=(n-1)/2$ and line $3$ is (if $n\geq 3$) $$(n-(n-1)/2+1)(n-1)/2=\frac{n+3}{2}\frac{n-1}{2}=\frac{n^2+2n-3}{4}\geq \frac{n^2}{4}$$