Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
1  
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

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.