求证：𝑂𝑓𝑛 + 𝑂𝑔𝑛 =𝑂ma𝑚𝑓𝑛 𝑔𝑛。

假设存在两个函数 $f(n)$ 和 $g(n)$，以及一个大于等于 $n_0$ 的正整数 $n_0$，满足：

• 对于所有大于等于 $n_0$ 的正整数 $n$，$f(n)$ 和 $g(n)$ 都是非负实数。
• 存在正数 $c_1$、$c_2$ 和 $n_1$，使得对于所有大于等于 $n_1$ 的正整数 $n$，有 $f(n) \leq c_1 \cdot \max(f(n), g(n))$ 和 $g(n) \leq c_2 \cdot \max(f(n), g(n))$。

我们需要证明存在正数 $c$ 和 $n_2$，使得对于所有大于等于 $n_2$ 的正整数 $n$，有 $\mathcal{O}(f(n)) + \mathcal{O}(g(n)) \leq c \cdot \max(f(n), g(n))$。

由于 $f(n)$ 和 $g(n)$ 都是非负实数，我们可以设 $h(n) = \max(f(n), g(n))$，则 $h(n)$ 也是非负实数。

由于 $\mathcal{O}(f(n))$ 表示存在正数 $c_3$ 和 $n_3$，使得对于所有大于等于 $n_3$ 的正整数 $n$，有 $f(n) \leq c_3 \cdot h(n)$。同理，$\mathcal{O}(g(n))$ 表示存在正数 $c_4$ 和 $n_4$，使得对于所有大于等于 $n_4$ 的正整数 $n$，有 $g(n) \leq c_4 \cdot h(n)$。

我们令 $c = c_1 + c_2$，$n_2 = \max(n_1, n_3, n_4)$，则对于所有大于等于 $n_2$ 的正整数 $n$，有：

$$ \begin{aligned} \mathcal{O}(f(n)) + \mathcal{O}(g(n)) &= c_3 \cdot h(n) + c_4 \cdot h(n) \ &= (c_3 + c_4) \cdot h(n) \ &\leq (c_1 + c_2) \cdot h(n) \ &= c \cdot \max(f(n), g(n)) \ \end{aligned} $$

因此，$\mathcal{O}(f(n)) + \mathcal{O}(g(n)) = \mathcal{O}(\max(f(n), g(n)))$。证毕