# Prove that for all $k \geq 1$, $\mathbb{log}(n)^k \in o(n)$ without using limits

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?

• $\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. – reuns Aug 23 '17 at 4:33

## 1 Answer

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.