Sum of Little-O Estimates/Sequences
Jump to navigation
Jump to search
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$