Substitution in Big-O Estimate/Sequences

Theorem

Let $(a_n)$ and $(b_n)$ be sequences of real or complex numbers.

Let $a_n = O(b_n)$ where $O$ denotes big-O notation.

Let $(n_k)$ be a diverging sequence of natural numbers.

Then $a_{n_k} = O(b_{n_k})$.

Proof

Because $a_n = O(b_n)$, there exists $M\geq0$ and $n_0 \in\N$ such that $|a_n| \leq M \cdot |b_n|$ for $n\geq n_0$.

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

Then $|a_{n_k}| \leq M\cdot |b_{n_k}|$ for $k\geq k_0$.

Thus $a_{n_k} = O(b_{n_k})$.

$\blacksquare$