Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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) ?


share|cite|improve this question
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$.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.