Show that if \(f(n)\) and \(g(n)\) are monotonically increasing functions, then so are the functions \(f(n) + g(n)\) and \(f(g(n))\), and if \(f(n)\) and \(g(n\)) are in addition nonnegative, then \(f(n) \cdot g(n)\) is monotonically increasing.
As \(f(n)\) and \(g(n)\) are monotonically increasing functions,
\[m \le n \implies f(m) \le f(n) \tag {1}\] \[m \le n \implies g(m) \le g(n) \tag {2}\]Therefore, \(f(m) + g(m) \le f(n) + g(n)\), i.e. \(f(n) + g(n)\) is monotonically increasing.
Also, combining (1) and (2), \(f(g(m)) \le f(g(n))\)
Therefore, \(f((g(n))\) is also monotonically increasing.
If \(f(n)\) and \(g(n\)) are nonnegative we can multiply inequalities (1) and (2), to say:
\[f(m) \cdot g(m) \le f(n) \cdot g(n)\]Therefore, \(f(n) \cdot g(n)\) is also monotonically increasing.