# A sequence which is not comparable to polynomials

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

-
Just mix a sequence like $(\log n)$ with a sequence like $(n!)$ to get what you are looking for. – martini Sep 21 '11 at 22:19
I don't see how that would give the desired behaviour, and what do you mean by mixing ? – Alephfour Sep 21 '11 at 22:27
Bounce back and forth from fast to slow: odd $n$ fast, even $n$ slow. – André Nicolas Sep 21 '11 at 22:30
$u_1 = 1$, then $u_2 = 2!$, then $u_{k+1} = (1 + 1/k^2) u_k$ until $u_k \le \log k$, then $u_{k+1} = (k+1)!$, etc. – Robert Israel Sep 21 '11 at 22:47
For non-decreasing, slow many times, huge jump, slow many times, huge jump, and so on. – André Nicolas Sep 21 '11 at 22:48

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$.