# Proving a basic limit

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!

-
You have to specify here that 'Alpha' is a constant . Other wise I can take Alpha=n . Then you will have n^n/2^n ---which tends to infinity as n tends to infinity. – B.Sahu Nov 27 '12 at 16:53
Oh, I didn't know that, thanks. – Dahn Jahn Nov 28 '12 at 8:44

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.

-
Thanks, this is nice and simple (although it did take me quite a while to go through it, hehe). – Dahn Jahn Nov 27 '12 at 14:57

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.

-
Thanks for the answer. I will have to go over the last bit for a while to fully comprehend it (just started series a week ago!), but I get the idea. – Dahn Jahn Nov 27 '12 at 14:31