1

I am having difficulty understanding how this follows.

$$(\log n)^{ (\log n) } = 2^{(\log n)(\log (\log n))} = n^{\log \log n}$$

Which logarithmic identities are used to go through each equality?

e.g. how do you first go from

$$(\log n)^{ (\log n) } = 2^{(\log n)(\log (\log n))}$$

and then to

$$2^{(\log n)(\log (\log n))} = n^{\log \log n}$$

(The log base must be 2 or else this equality won't hold)

T. Webster
  • 3,052

3 Answers3

6

I'm assuming the base is $2.$ Otherwise the equality doesn't hold.

$$2^{(\log n)(\log (\log n))} = 2^{(\log (\log n)) (\log n)} = (2^{(\log (\log n))})^{(\log n)}$$ and $$ 2^{(\log (\log n))} = \log n $$ because $$ 2^{\log x} = x.$$

Edit: to reflect the update in the question:

$$ 2^{(\log n)(\log (\log n))} = (\color{blue}{2^{(\log n)}})^{(\log (\log n))} = \color{blue}{n}^{{(\log (\log n))}} = n^{\log \log n} $$ because again $$ 2^{\log n} = n.$$

  • 1
    @T.Webster we have: $2^{ab} = 2^{ba} = (2^{a})^{b}.$ –  Jul 28 '12 at 18:06
  • 1
    @T.Webster it's equality. So you can either start from the right hand side or the left hand side. I started from the right hand side. $$2^{\log n \log \log n} = 2^{(\log \log n)\log n} = (2^{\log \log n})^{\log n} = (\log n)^{\log n}.$$ –  Jul 28 '12 at 18:10
  • @T.Webster wait few minutes, read other possible answers and then try to write down (with pencil & paper) the whole proof step by step. –  Jul 28 '12 at 18:12
  • 1
    @J.D. , isn't your answer taking $,\log =\log_2,$ ? – DonAntonio Jul 28 '12 at 18:19
1

For any $$1\neq a\in\Bbb R^+\,\,,\,\,x^y=a^{y\log_ax}\,\,,\,\text{whenever LHS is defined. }$$

Thus, $$(\log n)^{\log n}=2^{\log n\,\log_2(\log n)}$$

So your equality follows if the logarithm here is taken in base $\,2\,$ and not $\,10\,$ , as you wrote...

DonAntonio
  • 211,718
  • 17
  • 136
  • 287
1

Let

$$y=\log_2^{\log_2 n} n$$

Taking the logarithm (in base 2) of both sides

$$\log_2 y=\log_2 n \log_2 \log_2 n$$

Now, remember that $2^{\log_2 n}=n$. Thus

$$y=2^{\log_2 y}=2^{\log_2 n \log_2 \log_2}$$

Also recall that $a^{bc}=(a^b)^c$. Thus

$$y=2^{\log_2 n \log_2 \log_2 n}=(2^{\log_2 n})^{\log_2 \log_2 n}=n^{\log_2 \log_2 n}$$

Argon
  • 25,303