Substitution in Big-O Estimate/Sequences

Theorem

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

Let $a_n = \map \OO {b_n}$ where $\OO$ denotes big-O notation.

Let $\sequence {n_k}$ be a diverging sequence of natural numbers.

Then $a_{n_k} = \map \OO {b_{n_k} }$.

Proof

Because $a_n = \map \OO {b_n}$, there exists $M \ge 0$ and $n_0 \in \N$ such that $\size {a_n} \le M \cdot \size {b_n}$ for $n \ge n_0$.

Because $n_k$ diverges, there exists $k_0 \in \N$ such that $n_k \ge n_0$ for $k \ge k_0$.

Then $\size {a_{n_k} } \le M \cdot \size {b_{n_k} }$ for $k \ge k_0$.

Thus:

$a_{n_k} = \map \OO {b_{n_k} }$

$\blacksquare$