Prove Linearity in Asymptotic Notation The question: Prove O($\sum\limits_{k=1}^m(f_k(n))$) = $\sum\limits_{k=1}^m(O(f_k(n)))$
What I have done so far:
Left side: Let g(n) = O($\sum\limits_{k=1}^m(f_k(n))$)
For n > c, we have g(n) $\le$ C * ($f_1$(n) + $f_2$(n) + ... + $f_m$(n))
Right side: Let h(n) = $\sum\limits_{k=1}^m(O(f_k(n)))$
h(n) $\le$ O($f_1$(n)) + O($f_2$(n)) + ... + O($f_m$(n))
h(n) $\le$ $C_1$*$f_1$(n) + $C_2$*$f_2$(n) + ... + $C_m$*$f_m$(n)
From here I'm not sure what to do. I know I can't factor out the C's because they could be different.
I was thinking if I could prove O(f(n)) + O(g(n)) = O(f(n) + g(n)) I could related it to the above since it would kind of be like putting them all together but I don't even know how to do that
 A: You can definitely use the method used to prove O(f(n)) + O(g(n)) = O(f(n) + g(n)) to show what you want. But, you must also add the condition that f(n) and g(n) are greater than zero. I will prove this for you and leave it you to see how to apply it to the problem you presented.
Let the sequences $\left(f_{n}\right)$ and $\left(g_{n}\right)$
satisfy $f_{n}>0$ and $g_{n}>0$ for all $n\in\mathbb{N}$. Then
$\mathcal{O}\left(f_{n}\right)+\mathcal{O}\left(g_{n}\right)=\mathcal{O}\left(f_{n}+g_{n}\right)$.
Proof.Suppose 
$$
\varphi_{n}=\mathcal{O}\left(f_{n}\right)\quad\text{and}\quad\psi_{n}=\mathcal{O}\left(g_{n}\right).
$$
Then, by definition, there exist indices of these sequences $n^{\prime}\in\mathcal{\mathbb{N}}$
and $n^{\prime\prime}\in\mathbb{N}$ as well as constants $M_{1}>0$
and $M_{2}>0$ such that $\left|\varphi_{n}\right|\leq M_{1}f_{n}$
whenever $n>n^{\prime}$and $\left|\psi_{n}\right|\leq M_{2}g_{n}$whenever
$n>n^{\prime\prime}$. Thus, taking $n_{0}:=\max\left\{ n^{\prime},n^{\prime\prime}\right\} $,
it follows that 
$$
\left|\varphi_{n}+\psi_{n}\right|\leq\left|\varphi_{n}\right|+\left|\psi_{n}\right|\leq M_{1}f_{n}+M_{2}g_{n}
$$
for $n>n_{0}$. Now, taking the maximum of these two constants, i.e.,
$M:=\max\left\{ M_{1},M_{2}\right\} $, it follows that 
$$
\left|\varphi_{n}+\psi_{n}\right|\leq M\left(f_{n}+g_{n}\right)
$$
Thereby implying that $\varphi_{n}+\psi_{n}=\mathcal{O}\left(f_{n}\right)+\mathcal{O}\left(g_{n}\right)=\mathcal{O}\left(f_{n}+g_{n}\right)$.
