Sum of Little-O Estimates/Sequences

Theorem

Let $\sequence {a_n}, \sequence {b_n}, \sequence {c_n}, \sequence {d_n}$ be sequences of real or complex numbers.

Let:

$a_n = \map \oo {b_n}$

$c_n = \map \oo {d_n}$

where $\oo$ denotes little-$\oo$ notation.

Then:

$a_n + c_n = \map \oo {\size {b_n} + \size {d_n} }$

Proof

Let $\epsilon > 0$.

Then by definition of little-$\oo$ notation:

$\exists n_1 \in \N: \paren {n \ge n_1 \implies \size {a_n} \le \epsilon \cdot \size {b_n}}$

$\exists n_2 \in \N: \paren {n \ge n_2 \implies \size {c_n} \le \epsilon \cdot \size {d_n}}$

For $n \ge \max \set {n_1, n_2}$:

\(\ds \size {a_n + c_n}\)

\(\le\)

\(\ds \size {a_n} + \size {c_n}\)

Triangle Inequality

\(\ds \)

\(\le\)

\(\ds \epsilon \cdot \size {b_n} + \epsilon \cdot \size {d_n}\)

\(\ds \)

\(=\)

\(\ds \epsilon \cdot \size {\size {b_n} + \size {d_n} }\)

Absolute value is positive

Hence by definition of little-$\oo$ notation:

$a_n + c_n = \map \oo {\size {b_n} + \size {d_n} }$

$\blacksquare$