1
$\begingroup$

Prove that for all $k \geq 1$, $[\mathbb{log}(n)]^k \in o(n)$ without using limits, i.e prove that for any $c > 0$, there is a $n_0 > 0$ such that for all $n \geq n_0$, $[\mathbb{log}(n)]^k \lt cn$

I first proved it using limits and L'hopital's Rule by showing inductively that $\lim \frac{\mathbb{log}(n)^k}{n} = 0$ for any integer $k \geq 1$, but I'm not sure if my proof is right, and regardless, I need to prove the result without the use of limits.

I did the first part, but then I'm stuck and I don't know what to do with the power. I've been trying to solve this for hours.


First, we prove the case where $k=1$ by showing that $e^{cn} > n$, then taking the logarithms;

Let $c \geq 1$, then $e^{cn} \geq e^n$ and for all $n \geq 1$, $e^{cn} \gt n$ since $e^n =1+n+n^2 /2!+n^3 /3!+⋯ \gt n$. Otherwise, $ 0 \lt c \lt 1$, and for all $n \geq 2/c^2$, we have $e^{cn} = 1 + cn + c^2n^2/2 + c^3n^3/6 +... \gt c^2n^2/2 \geq (2/c^2)(c^2/2)n = n$, so $e^{cn} \gt n$.

Thus, for any $c > 0$, there is a $n_0 = \mathbb{max}(1,2/c^2)$ such that $e^{cn} \gt n$, or equivalently, $\mathbb{log}(n) \lt cn$ for all $n \geq n_0$, and by definition this means that $\mathbb{log}(n) \in o(n)$.


What to do from here?

$\endgroup$
  • $\begingroup$ $\log(n)^k \le n, \log(n) \le n^{1/k}, k \log(l) = \log(l^k) \le (l^k)^{1/k} = l$. Thus it reduces to $\lim_{l \to \infty} \frac{\log(l)}{l} = \lim_{a \to \infty} \frac{a}{2^a}=0$ even if you don't like it. $\endgroup$ – reuns Aug 23 '17 at 4:33
0
$\begingroup$

Let $n= x^k$, we need to prove $\log(x^k)^k = o(x^k)$, or $$k\log(x) = \log(x^k) = o(x),$$ which is what you just proved.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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