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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.