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