Suppose $f(n)=O(s(n))$ and $g(n)=O(r(n))$? All four functions are positive-valued and monotonically increasing. Using the formal definitions of asymptotic notations, prove or disprove the claim:
if $s(n)=O(g(n))$, then $f(n)=O(r(n))$
I can't seem to find any counter examples. Any guidance on how to prove this?
 A: Given
$$|f(n)| \le C_1 |s(n)| ~ ^{(1)}, \ \ |g(n)| \le C_2 |r(n)| ~ ^{(2)}, \ \ C_1, C_2, C_3 \in \mathbb{R}^+$$
Show that $\exists C \in \mathbb{R}^+:$
$$|s(n)| \le C_3 |g(n)| ~ ^{(3)} \implies |f(n)| \le C |r(n)| $$

Proof:
$$ |f(n)| \overset{(1)}\le C_1 |s(n)| \overset{(3)}\le C_1 C_3|g(n)| \overset{(2)}\le C_1 C_3 C_2 |r(n)|$$
Taking $C := C_1 C_3 C_2$, we see that
$$|f(n)| \le C|r(n)| \implies f(n)=O(r(n)) \ \ \ \ \square$$

Note: Since all functions are positive-valued you may just drop the modules.
A: This is, so called, transitivity of big-O:
$$f\in O(g) \land g\in O(h) \Rightarrow f \in O(h)$$
If we consider definition for positive sequences:
$$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, f(n)\leqslant C g(n)\}$$
then exact proof should manipulate with both constants in big-O definition i.e. $C,N$:
$f \in O(g)$ mean $\exists C_f>0, \exists N_f \in \mathbb{N}, \forall n>N_f, f(n)\leqslant C_f g(n)$.
Also, $g \in O(h)$ mean $\exists C_g>0, \exists N_g \in \mathbb{N}, \forall n>N_g, g(n)\leqslant C_g h(n)$.
Now if we take $N=\max(N_f,N_g)$, then for $\forall n>N$ we will have $$f(n)\leqslant C_f g(n) \leqslant C_f C_g h(n)=Ch(n)$$
where we take $C=C_f C_g$.
Having transitivity it's enough to apply it twice to chain $f\in O(s), s\in O(g), g \in O(r) \Rightarrow f \in O(r)$.
In set notations it produce
$$O(f) \subset O(s) \subset O(g) \subset O(r)$$
Note, please, that we do not need monotonic for this property.
