Prove/Disprove - If $f_1(n) = O(g_1(n))$ and $f_2(n) = O(g_2(n))$, then $f_1(n) + f_2(n) = O(g_1(n)+g_2(n))$

Question

I want to verify the following proof:

Suppose $f_1(n) = n^2$, and $f_2(n) = n + 1$

Then,

$f_1(n) = O(n^2)$

$f_2(n) = O(n)$

The lower order term cancels, thus: $f_1(n) + f_2(n) = O(n^2)$

Which disproves the conjecture

Answer 1

For your example,

$$f_1(n)+f_2(n)=O(n^2)$$

is a true statement.

However, that doesn't imply that

$$f_1(n)+f_2(n)=O(n^2+n)$$

is a false statement.

In fact, we know that $n^2 \leq n^2+n$.

That is $$f_1(n)+f_2(n)=O(n^2) \implies f_1(n)+f_2(n)=O(n^2+n)$$