I've come across challenge proof question in my discrete mathematics textbook that I'm trying to solve for practice but unfortunately it does not have a solution. Any help with a reasonable explanation or solution so that I can understand where to start and verify my work would be greatly appreciated:
Suppose that $f$, $g$ and $h$ are all functions from $\mathbf{N}$ into $\mathbf{R^+}$. Prove that if $f + g \notin O(h)$, then either $f > \notin O(h)$, or $g \notin O(h)$ (or both).
Recall that $f \in O(h)$ if and only if $\exists c \in \mathbf{R}^+, > \exists n_0 \in \mathbf{N}, \forall n \in \mathbf{N}, n \ge n_0 > \implies f(n) \le ch(n)$. We define $f + g$ to be the function such that $(f + g)(n) = f(n) + g(n)$ for every element $n$ of $\mathbf{N}$.
Thank you!
$f+g \not\in O(h)$ means that, for any $c > 0$, there is a value of $x$ such that $f(x)+g(x) > ch(x)$.
$f \in O(h)$ means that, for all large enough $x$, there is a $c > 0$ such that $f(x) < ch(x)$ and similarly for $g$.
If both $f \in O(h)$ and $g \in O(h)$ there are $c_f$ and $c_g$ such that, for all large enough $x$, $f(x) < c_fh(x)$ and $g(x) < c_gh(x)$.
Therefore, for all large enough $x$, $f(x)+g(x) \lt (c_f+c_g)h(x)$, so that $f+g \in O(h)$.