One question on my homework is as follows:
Let $f_1, f_2, f_3, f_4$ be functions from the set $N$ of natural numbers to the set $R$ of real numbers. Suppose that $f_1= O(f_2)$ and $f_3=O(f_4)$. Use the definition of Big Oh given in class to prove that $$f_1(n) + f_3(n) = O(\max(f_2(n), f_4(n))).$$
I have tried to go through the proof, first stating the obvious definitions of Big-$O$ for each of the two relationships listed above. In the next steps, I also tried assuming in one instance that $f_3 = O(f_1)$ and in another that $f_1 = O(f_3)$, to show the resulting relationship that $f_3 = O(f_2)$ and $f_1 = O(f_4)$, respectively. In both assumptions, however, I am unable to tie in BOTH $f_2$ and $f_4$, as is asked for in the question (e.g.$\max(f_2(n), f_4(n)))$). I am stuck.
For large n, $f_1 (n) ≤ c f_2 (n)$ and $f_2 (n) ≤ d f_4 (n)$.
You now use that $a + b ≤ 2 max (a, b)$:
For large n $f_1 (n) + f_3 (n)$ ≤ $c f_2 (n) + d f_4 (n)$ ≤ $(c+d) f_2 (n) + (c+d) f_4 (n)$ = $(c+d) (f_2 (n) + f_4 (n))$ ≤ $2 (c+d) max (f_2 (n), f_4 (n))$.
That means by definition $f_1 (n) + f_3 (n) + O (max (f_2 (n), f_4 (n))$.