Are two sequences comparable with big O notation if they are positive, decreasing and with limit $0$?

58 Views Asked by At

Let $a_n$ and $b_n$ be strictly positive and decreasing sequences such that $\lim a_n = \lim b_n = 0$.

Is it true that one of the following has to hold: $a_n = \mathcal O (b_n)$ or $b_n = \mathcal O(a_n)$?

Looking for a counter example i managed to constructed the following sequence but I am not sure if it is useful for my purpose. $c_n$ a decreasing positive function with limit zero. then

$a: \, c_2, c_2, c_4, c_4, c_6, c_6 \ldots$

$ b: \, c_1, c_3, c_3, c_5, c_5, c_7 \ldots$

2

There are 2 best solutions below

0
On BEST ANSWER

With $$a_n^{-1} = \begin{cases} 2\cdot (n+2)! &\text{if } n \text{ is odd} \\ (n+3)! &\text{if } n \text{ is even}\end{cases} \qquad\text{and}\qquad b_n^{-1} = \begin{cases} (n+3)! &\text{if } n \text{ is odd} \\ 2\cdot (n+2)! &\text{if } n \text{ is even} \end{cases}$$ we have two strictly decreasing sequences converging to $0$ with $$\frac{a_n}{b_n} = \begin{cases} \dfrac{n+3}{2} &\text{if } n \text{ is odd} \\ \dfrac{2}{n+3} &\text{if } n \text{ is even}\end{cases}\,,$$ so neither $b_n = \mathcal{O}(a_n)$ nor $a_n = \mathcal{O}(b_n)$.

1
On

$a_n =O(b_n) $ means there is a $c > 0$ such that, for large enough $n$, $a_n < cb_n $ or $b_n/a_n > 1/c$.

If this does not hold, then $b_n/a_n \to 0$.

Similarly, if $b_n \ne O(a_n)$ then $a_n/b_n \to 0$.

These can not both hold because they imply that, for large enough $n$, $a_n < \epsilon b_n$ and $b_n < \epsilon a_n$ so that $a_n < \epsilon^2 a_n$ which is false for $\epsilon < 1$.

Therefore one of $a_n=O(b_n)$ or $b_n=O(a_n)$ must hold.