big O notation with asymptotically nonnegative increasing functions 
Let $f(n)$ and $g(n)$ be asymptotically nonnegative increasing functions. Show:
  $f(n) · g(n) = O((\max\{f(n), g(n)\})^2)$, using the deﬁnition of big-oh.

I can't quite figure this out, can someone help explain why this is true?
 A: We have $f(n)\leq \max\{f(n),g(n)\}$ and $g(n)\leq \max\{f(n),g(n)\}$. As $f(\cdot)$ and $g(\cdot)$ are non-negative, we get $$f(n)\cdot g(n)\leq \max\{f(n),g(n)\}^2,$$
what is wanted (take the constant equal to $1$ in the definition).
A: Another way, though with a worse constant:
Once $f$ and $g$ are positive,
$f g
=(f+g)^2-f^2-g^2
$,
so
$\begin{align}
|fg|
&\le (f+g)^2+f^2+g^2\\
&\le (2\max(f, g))^2+2(\max(f,g))^2\\
&= 6(\max(f, g))^2\\
&= O(\max(f, g))^2\\
\end{align}
$
A: Here is a proof that minimizes the number of 'surprises', i.e., one which I designed by just following the shape of the formulae.
Directly using the definition, I would calculate
\begin{align}
& f(n) \times g(n) = O((f(n) \text{ max } g(n))^2) \\
\equiv & \qquad \text{"definition of $\;O\;$"} \\
& \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le (f(n) \text{ max } g(n))^2 \rangle \rangle \\
\equiv & \qquad \text{"square of max = max of squares, since $\;f(n) \ge 0\;$ and $\;g(n) \ge 0\;$, for l.e. $\;n\;$"} \\
& \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le f(n)^2 \text{ max } g(n)^2 \rangle \rangle \\
\equiv & \qquad \text{"basic property of $\;\text{max}\;$"} \\
& \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: k \times f(n) \times g(n) \le f(n)^2 \;\lor\; k \times f(n) \times g(n) \le g(n)^2 \rangle \rangle \\
\equiv & \qquad \text{"divide by $\;f(n)\;$, which is $\;\ge0\;$ for l.e. $\;n\;$; same for $\;g(n)\;$"} \\
& \langle \exists k : k > 0 : \langle \forall_{l.e.} n :: f(n) = 0 \;\lor\; k \times g(n) \le f(n) \\
& \phantom{\langle \exists k : k > 0 : \langle \forall_{l.e.} n ::} \lor\; g(n) = 0 \;\lor\; k \times f(n) \le g(n) \rangle \rangle \\
\Leftarrow & \qquad \text{"choose $\;k := 1\;$ -- this seems the simplest most symmetrical choice"} \\
& \langle \forall_{l.e.} n :: f(n) = 0 \;\lor\; g(n) \le f(n) \;\lor\; g(n) = 0 \;\lor\; f(n) \le g(n) \rangle \\
\equiv & \qquad \text{"real numbers are a total order, i.e., $\;x \le y \;\lor\; y \le x\;$"} \\
& \text{true}
\end{align}
Note that this proof only assumes that $\;f,g\;$ are eventually non-negative: we did not need to assume that they are increasing.
