Proving $\lim_{n\to \infty}\frac{n^\alpha}{2^n}=0, \alpha>1$

Question

I'm attempting to prove a basic limit: $$\lim_{n\to \infty}\frac{n^\alpha}{2^n}=0, \alpha>1$$ (It seems like this should be here somewhere already, but I wasn't able to found it through search, I possibly need help with my searching skills? :)

Here's what I came up with:

A) There are $\alpha$ powers of $n$ in the numerator (duh).

B) $2^n=(1+1)^n=1+n+\binom{n}{2}+\cdots+\binom{n}{n-1}+1$

C) The highest power of $n$ in the denominator is $\lfloor\frac{n}{2}\rfloor$ (from the binomial theorem)

D) Thus the power of $n$ in the denominator grows indefinitely, while in the numerator it always stays $\alpha$.

If these are true, it then follows that for some $n_0$ and all $n>n_0$, $2^n$ grows faster than $n^\alpha$ and the limit approaches zero.

However, this is very vague and possibly untrue, and this is where I got stuck. Thanks a lot for any help!

Answer 1

Actually, you only need to modify the part C. Though $2^n$ does not grow as fast as $n^{n/2}$, we can still show that $2^n$ grows faster than $n^{\alpha}$ for any fixed $\alpha$.

Fix a positive integer $m > \alpha$. Then for $n \geq m$ we have

$$2^n = (1+1)^n \geq \binom{n}{m} = \frac{n(n-1)\cdots(n-m+1)}{m!} = \frac{n^{m}}{m!}\left(1 - \frac{1}{n}\right)\cdots\left(1 - \frac{m-1}{n}\right). $$

This already confirms that $2^n$ grows faster than $C_{m} n^{m}$ for some $C_m > 0$ if $n$ is large. Then we have

$$ 0 \leq \frac{n^{\alpha}}{2^n} \leq \frac{n^{\alpha}}{n^m} \cdot m! \left(1 - \frac{1}{n}\right)^{-1} \cdots \left(1 - \frac{m-1}{n}\right)^{-1}, $$

thus the conclusion follows by the squeezing lemma.

Answer 2

Your claim that the highest power of $n$ in the denominator is $r=\lfloor n/2 \rfloor$ is not true. You can check yourself that $n^r$ actually grows faster than $2^n.$

Instead, we can consider the ratio of consecutive terms of this sequence. $$ \frac{(n+1)^{\alpha} }{2^{n+1} } \cdot \frac{2^n}{n^{\alpha}}= \frac{1}{2} \left( 1+ 1/n\right)^{\alpha}.$$

For large enough $n$, this ratio remains less than, say, $3/4$, which implies that there is a geometric series of common ratio $3/4$ (so tending to 0) that bounds this sequence from above, and by the squeeze theorem this sequence goes to 0 as well.

Answer 3

You can also always use L'Hopital's Rule. In case you are not familiar, L'Hoptial's Rule states that if you are evaluating a limit $\lim_{n \to \infty} \dfrac{f(x)}{g(x)}$ and, as written, this "evaluates" to an "indeterminate form" (examples are $\infty / \infty$, $0/0$, basically anything that doesn't cleary diverge or converge) then

$$\lim_{x \to \infty} \dfrac{f(x)}{g(x)} = \lim_{n \to \infty} \dfrac{f^\prime(x)}{g^\prime(x)}$$

(of course, also assuming $f$ and $g$ are differentiable.) Using this rule, repeated differentiation can reduce the problem to a limit that trivially goes to 0. Clearly I didn't really use the formal terminology for everything but I think this should get the idea across.