Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|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
2  
$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
2  
For non-decreasing, slow many times, huge jump, slow many times, huge jump, and so on. –  André Nicolas Sep 21 '11 at 22:48
show 3 more comments

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.