3
$\begingroup$

I am searching for an explicit example of a sequence of real numbers $(u_n)$ that satisfies the following properties:

(1) for any $\alpha>0$, $n^{\alpha}\notin \mathcal{O}(u_n)$,

(2) There exists $\beta>0$ such that $u_n \notin \mathcal{O}(n^\beta)$.

(3) [Edited after comments] $(u_n)$ is non-decreasing

It might be easy, but I didn't find any of such $(u_n)$. For instance $\log(n)$ satisfies (1,3) but not (2). Could it be that (1,3) implies not (2) ?

Thanks

  • 2
    For non-decreasing, slow many times, huge jump, slow many times, huge jump, and so on.2011-09-21

1 Answers 1

2

For an explicit expression, try $ u_n=2^{2^{2^{\lfloor\log_2\log_2\log_2 n\rfloor+1/2}}} $ (valid for $n\ge4$). For positive integer $a$, if $n=2^{2^{2^a}}$ then $u_n=2^{2^{2^a\sqrt2}}=n^{2^{2^a(\sqrt2-1)}}$, which is faster than $n^\alpha$, any $\alpha > 0$. Also, $u_{n-1}=2^{2^{2^a/\sqrt2}}=n^{2^{-2^a(1-1/\sqrt{2})}}$, which is much slower than $n^\alpha$.

Note: This is just an explicit realization of André's suggestion of slow many times, huge jump, etc.