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

Question

The left hand side stands for a single function $f(i)$ in $\Theta(i)$ summed over $i=1,\,2,\,3,\,\ldots,\,n$. I know it is sufficient to show that $h_1(n)\leq\sum_{i=1}^nf(i)\leq h_2(n)$ for all sufficiently large $n$, where $h_1(n)=\Omega(n^2)$ and $h_2(n)=O(n^2)$ but I'm not exactly sure how to prove this.

Answer 1

So we have $f(n)\in\Theta(n)$, i.e. there is $k_1,k_2>0$ such that

$$k_1n\leq f(n)\leq k_2n$$

eventually. Now lets add those inequalities to each other for consecutive $n$, then we get

$$\sum_{i=1}^n k'_1i \leq\sum_{i=1}^nf(i)\leq \sum_{i=1}^n k'_2i$$

Note that since the initial inequality is "eventually" (i.e. starting from some $n_0$) then it may happen that we need to reduce $k_1$ to $k'_1$ and increase $k_2$ to $k'_2$ (i.e. consider what's going on for $n<n_0$). Anyway I leave as an exercise that such $k'_1,k'_2>0$ can be chosen so that they will work eventually as well (i.e. the further we go, the less initial $n_0$ terms matter).

And so we get

$$k'_1\frac{n(n+1)}{2}\leq\sum_{i=1}^nf(i)\leq k'_2\frac{n(n+1)}{2}$$

which shows that $\sum_{i=1}^n f(i)$ is $\Theta\big(\frac{n(n+1)}{2}\big)=\Theta(n^2)$.