# Is the a sum of theta same as theta of a sum?

The header could probably be phrased better...

My teacher used the following claim: $$\sum_{i=1}^{n}\theta\left(i\right)=\theta\left(\sum_{i=1}^{n}i\right)$$

It was in an introduction to algorithms course. Theta refers to the asymptomatic notation. Same as big O.

It looked trivial at first, but after thinking about it, im not sure it's true. Or how to prove it.

Assistance would be appreciated

• Without knowing what $\theta$ is it is impossible to say. – copper.hat Oct 26 '18 at 13:08
• Theta as in asymptomatic notation. It's from a course in algorithms – AK_ Oct 26 '18 at 13:11

A function $$f:\mathbb{N} \to \mathbb{R}$$ is said to be $$\Theta(n)$$ iff there is some $$N$$, $$c_2 \ge c_1 > 0$$ such that $$c_1 n \le f(x) \le c_2 n$$ for all $$n \ge N$$.
Suppose $$f$$ is $$\Theta(n)$$, and $$n \ge N$$. Let $$K = f(1)+\cdots+f(N-1)$$ and $$S_n = 1+\cdots + n$$.
Then we have $$c_1 \sum_{k=N}^n n +K = c_1 (S_n-S_{N-1}) +K \le \sum_{k=1}^n f(n) \le c_2 \sum_{k=N}^n n +K = c_2 (S_n-S_{N-1})+K$$.
Note that $$c_2 (S_n-S_{N-1})+K \le (c_2+K) S_n$$, so we have an upper bound.
The lower bound needs a little more finesse: Since $$c_1 (S_n-S_{N-1}) +K = S_n ( c_1 -c_1 {S_{N-1} \over S_n} + {K \over S_n})$$, and $$(-c_1 {S_{N-1} \over S_n} + {K \over S_n}) \to 0$$, we can choose $$N' \ge N$$ such that $$(-c_1 {S_{N-1} \over S_n} + {K \over S_n}) \le {1 \over 2} c_1$$ and so $$c_1 (S_n-S_{N-1}) +K \ge {1 \over 2 } c_1 S_n$$.
Hence for $$n \ge N'$$ we have $${1 \over 2 } c_1 S_n \le \sum_{k=1}^n f(n) \le (c_2+K) S_n$$.