Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Limit of n^2/2^n as n Tends to Infinity

Date: 12/05/2002 at 09:39:42
From: Alex Kamajian
Subject: Limit of n^2  /  2^n as n tends to infinity

How would you demonstrate that the limit as n tends to infinity of 
the fraction n^2 / 2^n = 0 ?

I started by taking the log to the base 2 of n^2 / 2^n and assuming 
that 2 log n - n < 0.

I then wrote the inequality as n <= 2^(n/2) and used induction to 
convince myself that this last is true in general.

The problem I have with this 'proof' is that I have merely 
transformed the original problem. Any ideas?

I found the problem in one of those Advanced Calculus review books. 
The problem was listed in a chapter covering sequences and appeared 
before l'Hospital's rule was discussed. 

I attempted to determine the limit using things like Bernoulli's 
inequality [ (1 + x)^n >= 1 + n*x ] like the examples in the chapter. 
I was inclined NOT to use l'Hospital's rule in hopes of taking the 
limit AFTER manipulating the expression algebraically to get the 
desired result.

Do you have any suggestions on how to handle this limit using 
algebraic manipualtions and/or inequality?


Date: 12/07/2002 at 18:28:30
From: Doctor Schwa
Subject: Re: Limit of n^2  /  2^n as n tends to infinity

Hi Alex,

To prove the inequality n <= 2^(n/2) is not so hard, but does that 
prove that the limit is 0, or only that the limit is less than 1?

To prove your inequality, induction will do great. If it's true for n 
(and it IS true when n = 6 or 7, you can check), then prove it's true 
for n + 2 (one side you add 2, the other side DOUBLES, so that's
pretty clear).

I'd still use L'Hopital's rule, it's much easier that way!

But of course there must always be another way.

Here's one somewhat awkward method.

Let's let the nth term of this thing be called a(n), and prove that 
after a little while, the ratio a(n + 1)/a(n) is always less than, 
say, 3/4, and hence the limit is less than (3/4)^n, and thus 0.

In particular, looking at the first few terms, 1/2, 4/4, 9/8, it's 
still increasing, but 16/16, 25/32, now it's decreasing, but not by 
much, 36/64, and in fact from now on the ratio is less than 3/4 
(approaching, but never reaching, 1/2.)

Proof:
if n > 6, then
a(n + 1) / a(n) = ((n + 1)^2 / 2^(n + 1)) / (n^2 / 2^n)
   = (n^2 + 2n + 1) / (2n^2)
   = 1/2 + 1/n + 1/2n^2
   < 1/2 + 1/6 + 1/72
   < 3/4.

Thus for n > 6, a(n) < a(6) * (3/4)^(n - 6), which clearly approaches 
0, since it's a constant times a decaying exponential.

Does that help?

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 


Date: 12/10/2002 at 10:19:35
From: Alex Kamajian
Subject: Limit of n^2  /  2^n as n tends to infinity

After thumbing through some other material I tried the following.

I started by rewriting n^2/2^n as [ n / SQRT(2^n) ]^2 or equivalently 
as [ n / SQRT(2)^n ]^2 ] and then determined the limit of the 
expression in the square brackets.

Setting SQRT(2) = 1 + h, [SQRT(2)]^n > [ n(n - 1)h^2 ] / 2 or
1 / [SQRT(2)]^n < 2 / [ n(n - 1)h^2 ] by Bernoulli's inquality.

Putting all this together n / [SQRT(2)^n] < 2n / n(n - 1)h^2 or
n / [SQRT(2)^n] < 2 / (n - 1)h^2.

So as n tends to infinity n / [SQRT(2)^n] tends to zero (0) which 
implies that n^2/2*n tends to zero (0) as n tends to infinity.

I think I have this right but I agree with you that l'Hospital's rule 
takes less effort to produce the same result.

Thanks for following up.


Date: 12/11/2002 at 00:54:16
From: Doctor Schwa
Subject: Re: Limit of n^2  /  2^n as n tends to infinity

Yes, this method works.

You might as well not do the awkward square root step but just say 
that by Pascal's triangle (1 + 1)^n > (n)(n - 1)(n - 2)/6.

That's actually a rather simple argument, now that I see it: it proves 
that 2^n > n^k for any constant k, since 2^n > (n choose k + 1) which 
is a polynomial of degree k+1 which thus outgrows any polynomial of 
degree k.

I like it! Thanks for sharing your idea.

- Doctor Schwa, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Calculus

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/