Proving $\log^n(n)=\omega(n^{\log(n)}) $

Question

Proving $\log^n(n)=\omega(n^{\log(n)}) $

Hey everyone. I am trying to prove that $\displaystyle\lim_{n\to\infty}\frac{(\log n)^n}{n^{\log n}}=\infty $

(here $\log n= \log_2 n$)

I've tried proving this using squeeze theorem, since using L'Hôpital's rule in this case is quite out of question. I thought of proving this using the definition: $\log^n(n)=\omega(n^{\log(n)}) \iff \forall C>0 \ \ \exists N>0$ s.t. $ \forall n\ge N , (\log n)^n \ge C \cdot n^{\log n} $

Let $C$ be some arbitrary positive value. Then we can say that for all $n \ge 2^C \implies (\log n)^n>C^{2^C} $

and $ n^{\log n} \ge 2^{C^2} $

If $C>2$ then $C^{2^C} \ge 2^{C^2} $ (How can I elegantly prove this?) $\implies (\log n)^n \ge n^{\log(n)} \ , \ \forall n\ge 2^C$

Else, $0\lt C \lt 2 $... I'm quite lost and not sure if this direction is alright. I would love to hear your thoughts. Thank you :)

Answer 1

Let $g(n)=\frac {(\log n)^n}{n^{\log n}}.$

Then $$\log g(n)=n(\log n)-(\log n)(\log n)=(n-\log n)(\log n).$$

As long as your $\log$ is to a base $B>1$, we have $n-\log n\to \infty$ and $\log n \to \infty$ so $\log g(n) \to \infty$ so $g(n)\to \infty.$

Answer 2

Hint: Using $a^b = 2^{b \log_2 {a}}$, we see that $(\log_2 n)^n = 2^{n\log_2 n}$ and $n^{\log_2 n} = 2^{(\log_2 n)^2}$. Hence the ratio you are interested in is equal to $$2^{n\log_2 n - (\log_2 n)^2} = 2^{(\log_2{n}) (n - \log_2 n)}.$$ Can you explain why this tends to $\infty$ as $n\to \infty$?