How to prove that $\lim_{n\to \infty} (n^k/2^n) = 0$?

Question

I'm having a hard time trying to prove this statement.

$\lim_{n\to \infty} (n^k/2^n) = 0$

k is a positive number.

Please, help me.

Thanks in advance.

Answer 1

Use L'Hôpital's rule (since $\displaystyle \lim_{n \to \infty}{n^{k}} = \infty$ and $\displaystyle \lim_{n \to \infty}2^{n} = \infty$);

$\displaystyle \lim_{n \to \infty}\frac{n^{k}}{2^{n}} = \lim_{n \to \infty}\frac{kn^{k-1}}{2^{n}\text{ln(2)}}$.

If $k$ is a positive integer, repeat L'Hôpital's rule $k$ times overall;

$\displaystyle \lim_{n \to \infty}\frac{n^{k}}{2^{n}} = \lim_{n \to \infty}\frac{k!}{2^{n}(\text{ln(2)})^{k}} = \frac{k!}{(\text{ln(2)})^{k}}\displaystyle \lim_{n \to \infty}\frac{1}{2^{n}} = 0$.

Now, how does this change if $k$ is a positive real number, not an integer?

Answer 2

Hint: It's an indeterminate form $\frac{\infty}{\infty}$, and you can attempt L'Hopital's rule. One application changes the situation a little: it is the same indeterminate form, but instead of $n^k$ you have $kn^{k-1}$. Don't forget you can apply L'Hopital's rule to this new expression (and several times more, if necessary!)

Answer 3

$2^n=(1+1)^n>{n\choose\lceil\frac{n}{2}\rceil}$. So $$\frac{n^k}{2^n}<\frac{n^k}{n\choose\lceil\frac{n}{2}\rceil}\rightarrow0~(n\rightarrow\infty)$$

Answer 4

If you don't want to apply L'Hopital rule just note that $$\lim_{n \to \infty} \frac{n^k}{2^n} = \lim_{n \to \infty}\frac{e^{k\log n}}{e^{n\log 2}} = \lim_{n \to \infty}e^{k\log n - n \log 2} = e^{\lim_{n \to \infty}k\log n - n \log 2}$$ and you can now try to show that $$\lim_{n \to \infty}k\log n - n \log 2 = -\infty.$$

Answer 5

Let us prove that $\lim_{n \to \infty}\frac{n^k}{a^n}=0,$ for $a>1$. Let $m \in Z$ and $m>k$, then $$ 0<\frac{n^k}{a^n}\le \frac{n^m}{a^n}=\left(\frac{n}{\sqrt[m]{a^n}}\right)^m=\left(\frac{n}{b^n} \right)^m $$ where $b=\sqrt[m]{a}>1$. Now, \begin{align*} 0<\frac{n}{b^n}&=\frac{n}{(1+(b-1))^n}=\frac{n}{\sum\limits_{k=0}^n {n \choose k}1^{n-k}(b-1)^k}\\ &=\frac{n}{1+n(b-1)+\frac{n(n-1)}{2}(b-1)^2+\cdots+(b-1)^n} \\ &<\frac{n}{\frac{n(n-1)}{2}(b-1)^2} = \frac{2}{(b-1)^2(n-1)} \rightarrow 0 ~ (n \to \infty) \end{align*} Since $\frac{n}{b^n} \rightarrow 0 \Rightarrow (\frac{n}{b^n})^m \rightarrow 0~(n \to \infty)$

From $0<\frac{n^k}{a^n}\le \frac{n^m}{a^n}=\left(\frac{n}{\sqrt[m]{a^n}}\right)^m=\left(\frac{n}{b^n} \right)^m$, we have that $$\frac{n^k}{a^n} \rightarrow 0~ (n \to \infty) $$