4
$\begingroup$

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!

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – B.Sahu Nov 27 '12 at 16:53
  • $\begingroup$ Oh, I didn't know that, thanks. $\endgroup$ – Dahn Nov 28 '12 at 8:44
5
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, this is nice and simple (although it did take me quite a while to go through it, hehe). $\endgroup$ – Dahn Nov 27 '12 at 14:57
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ – Dahn Nov 27 '12 at 14:31
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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