How can I prove limit of $n^k$ over $c^n$ is 0?

Question

How can I prove that $$ \lim_{n \to \infty}\frac{n^k}{c^n}=0\ ? $$ I know it is true by intuition, but I do not know how to prove it. Here $c\gt1, k\ge1$.

---

BACKGROUND

I am learning time complexity theory and I couldn't find the proof of this in CLRS. It just shows that time complexity of $c^n$ is always greater than $n^k$. Therefore, I cannot understand the proof which uses derivatives like L'Hopital's rule.

Answer 1

Without loss of generality, let $k$ be an integer (or take $k$ to be floor[$k+1$]. Apply L'Hopital's rule $k$ times:

$\displaystyle \lim_{n \rightarrow \infty } \frac{n^k}{c^n} = \lim_{n\rightarrow \infty }\frac{k!}{(\ln c)^k c^n} = 0.$

Answer 2

Hint:

Set $u_n= \dfrac{n^k}{c^n}$ and calculate $\;\dfrac{u_{n+1}}{u_n}$ to find an upper bound of the ratio for $n$ large.

Answer 3

L'Hôpital's rule, applied to this case, says that for $f(n) = n^k$ and $g(n) = c^n$, since $\lim_{n \to \infty} f(n) = \infty$ and $\lim_{n \to \infty} g(n) = \infty$ and both $f$ and $g$ are differentiable, then $$\lim_{n \to \infty} \frac{f(n)}{g(n)} = \lim_{n \to \infty} \frac{f'(n)}{g'(n)}\ . $$

Thus, after applying L'Hôpital's rule $k$ times you get: $$\lim_{n \to \infty} \frac{k!}{(\ln c)^k c^n} = 0\ .$$

Answer 4

You may proceed for example as follows:

• $c > 1 \Rightarrow c = 1+p$ with $p > 0$

The binomial formula gives for $n \geq 1$

• $c^n = (1+p)^n = \sum_{i=0}^n\binom{n}{i}p^i \Rightarrow c^n > \binom{n}{i}p^i$ for each $i = 0,\ldots , n$

Now, you can estimate as follows for $n > k$:

\begin{eqnarray*} 0\leq \frac{n^k}{c^n} & = & \frac{n^k}{(1+p)^n}\\ & < & \frac{n^k}{\binom{n}{k+1}p^{k+1}}\\ & = & \frac{n^k\cdot (k+1)!}{\underbrace{n(n-1)\cdots (n-k+1)}_{k \; factors} \cdot (n-k) \cdot p^{k+1}} \\ & < & \frac{n^k\cdot (k+1)!}{(n-k)^{k+1} \cdot p^{k+1}}\\ & = & \frac{1}{n}\cdot \frac{(k+1)!}{(1-\frac{k}{n})^{k+1} \cdot p^{k+1}}\\ & \stackrel{n \to \infty}{\longrightarrow} & 0 \cdot \frac{(k+1)!}{p^{k+1}} = 0 \end{eqnarray*}

Answer 5

Two hints/ideas: try Stolz-Cesaro or consider the series with your expression as general term. If converges, the g.t. -> 0.