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
Math Forum Home || Math Library || Quick Reference || Math Forum Search