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.

Consider the following question I came across:

Let $n$ be a large integer. Which of the following statements is TRUE?

  1. $n^{1/\sqrt{\log_2 n}} < \sqrt{\log_2 n} < n^{1/100}$

  2. $n^{1/100} < n^{1/\sqrt{\log_2 n}} < \sqrt{\log_2 n}$

  3. $n^{1/\sqrt{\log_2 n}} < n^{1/100} < \sqrt{\log_2 n}$

  4. $\sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}} < n^{1/100}$

  5. $\sqrt{\log_2 n} < n^{1/100} < n^{1/\sqrt{\log_2 n}}$

To me the answer seems to be: $$ n^{1/100} < \sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}}$$

and limited empirical investigations also point in similiar direction. But this answer is not a part of the given options. Can I safely conclude that the options are invalid or am I missing something? I do not have access to solutions.

share|improve this question
    
You seem to have reversed the order of the terms in this inequality. Which way around is correct? –  Simon Hayward Dec 4 '12 at 13:08
    
@SimonHayward Can't get what you are saying, but the 5 options given are exactly the same in the printed material I have. And that is the questions, Can I conclude that the options are invalid? –  WeaklyTyped Dec 4 '12 at 13:11
    
??? The answer you have suggested is not one of the options you give in the question. You have changed the order of some of the terms. –  Simon Hayward Dec 4 '12 at 13:12
    
@SimonHayward Read the last paragraph of the post, you will realise what my dilemma is! –  WeaklyTyped Dec 4 '12 at 13:13
    
D'oh! I would suggest you are missing something. Have you tried searching for errata online? –  Simon Hayward Dec 4 '12 at 13:14

1 Answer 1

up vote 2 down vote accepted

Let take the logarithm of your three expressions \begin{align*} \log_2 n^{1/100} &= \frac 1{100} \log_2 n\\ \log_2 \sqrt{\log_2 n} &= \frac 12 \log_2\log_2 n\\ \log_2 n^{1/\sqrt{\log_2 n}} &= \frac 1{\sqrt{\log_2 n}} \log_2 n\\ &= \sqrt{\log_2 n} \end{align*} For $n$ big, we have $$ \log_2\log_2 n < a \sqrt{\log_2 n} < b\log_2 n $$ regardless of $a$ and $b$. As taking logarithms and exponentiating are monotone, therefore $$ \sqrt{\log_2 n} < n^{1/\sqrt{\log_2 n}} < n^{1/100}. $$

share|improve this answer
    
But the plots give different perspective (see the three links in OP) –  WeaklyTyped Dec 4 '12 at 13:18
1  
A plot can't give you anything about the behaviour for very big $n$. –  martini Dec 4 '12 at 13:19
    
Lets plug in powers of $2$ ... for $n = 2^k$, we have $\sqrt{\log_2 n} = \sqrt k$, $n^{1/\sqrt{\log_2 n}} = 2^{\sqrt k}$ ... and $n^{1/100} = 2^{k/100}$. You have $10^{100} \sim 2^{330}$, so $k = 330$, here: $\sqrt k \sim 18$, $2^{k/100} \sim 2^{3.3}$ ... but letting $k$ bigger will show you that you are wrong. –  martini Dec 4 '12 at 13:24
1  
Ok, I get the point. At some point we will have $n > k$ where $\sqrt{\log_2 k} > 100$ and post that point the inequality: $n^{1/\sqrt{\log_2 k}} < n^{1/100}$ will hold. Thanks! –  WeaklyTyped Dec 4 '12 at 13:29

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.