(n )/(2 ^n ) sequence limit problem

  • #1
1,235
1
Hello all

If I have a sequence: (n )/(2 ^n )

and I have already proved the lim (n)/ (2^n) = 0
n->00

then how would I find a number N such that (n)/ (2^n) < 1/ 10 ( or any other epsilon)? In other words how would I solve this equation?

Any help would be greatly appreciated

Thanks
 

Answers and Replies

  • #2
1,357
0
You can't really solve this kind of equation (at least to my knowledge). Looks like you're stuck using trial and error.
 
  • #3
1,235
1
But that would take a long time (its in Courants book)
 
  • #4
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
Prove by induction that for n>=4, [tex]2^{\frac{n}{2}}\geq{n}[/tex]
1. n=4:
[tex]2^{\frac{4}{2}}=4\geq4[/tex]
2. Let it be true for n=k>=4.
Then,
[tex]2^{\frac{k+1}{2}}=\sqrt{2}2^{\frac{k}{2}}\geq(1+\frac{1}{4})k\geq(k+1)[/tex]
QED
 
  • #5
1,235
1
Yea but I am trying to solve for n not prove that its true
 
  • #6
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
That was not the point!
Were you unable to see the trivial consequence:
[tex]\frac{n}{2^{n}}\leq\frac{2^{\frac{n}{2}}}{2^{n}}=\frac{1}{2^{\frac{n}{2}}}[/tex]
 
  • #7
1,235
1
How did you even get that? You suddenly threw a proof of induction. But why did you prove it for n/2? I do not understand how you arrived at the so called "trivial" consequence.
 
  • #8
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
Do you agree that I've proven that for n>=4, we have:
[tex]n<=2^{\frac{n}{2}}[/tex]?
 
  • #9
1,235
1
In general, let us say we have ( n )/( a ^ n)

For the above problem wouldnt you take the square root of the sequence as such:

sqrt (n) / sqrt ( 2^n)

sqrt(2) = 1 + h

= sqrt(n) / (1+h) ^n <= sqrt(n) / (1 + nh ) <= sqrt(n) / nh

= 1 / nh^2

Could I solve for n using this method? Thank you for all your help
 
  • #10
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
Sorry I was a bit snappish earlier.
Can we focus on your first problem before generalizing?
 
  • #11
1,235
1
Yeah, its ok. It's just that in my textbook I think they want me to use a certain method like the one mentioned above. I can see that your method by proof of induction works. Do you think that method mentioned above could work for solving n? Again thanks for all your input!
 
  • #12
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
132
Frankly, I can't make head or tails of your approach (might be cause I'm tired)

Now, there wasn't anything crucial about proving it for n/2, if that's something you might believe (you could just as easily make an induction argument on n/3 or 123/758n, for that matter).
The crucial idea is that an "exponential" grows faster than a "polynomial"
That is, an exponential function (as long as the base is greater than one) will always catch up with a polynomial. That's essentially the main idea behind the induction proof.
 
  • #13
1,235
1
More Limits

Hello again. Here is the problem. In each one we are defining smaller and smaller epsilons. Can you please help? Also what if you had n^2 / 2^n = 0?
 

Attachments

  • #14
HallsofIvy
Science Advisor
Homework Helper
41,833
956
At the very first, trial and error were suggested. Why did you declare "that would take too long"? It takes a heckofalot less time than reading all of these posts!

f(n)= n/2n

n f(n)
1 1/2
2 2/4= 1/2
3 3/8
4 4/16= 1/4
5 5/32= .15625
6 6/64= .09375 and we're done.

n= 6.
 
  • #15
1,235
1
HallsofIvy you are correct but here is the problem:

The other problems choose epsilon smaller and smaller such as:

(n/2^n) < 1/100
(n/2^n) < 1/1000

How would I find n now? Guess and check would take a very long time. I know by the definition of convergence:

|(n/ 2^n)| < 1/100 (for example) for ever N(epsilon) > n. So when I choose epsilon smaller and smaller, n will become larger and larger. Can someone please help me?

THanks a lot
 
  • #16
NateTG
Science Advisor
Homework Helper
2,450
5
courtrigrad said:
HallsofIvy you are correct but here is the problem:

The other problems choose epsilon smaller and smaller such as:

(n/2^n) < 1/100
(n/2^n) < 1/1000

How would I find n now? Guess and check would take a very long time. I know by the definition of convergence:

|(n/ 2^n)| < 1/100 (for example) for ever N(epsilon) > n. So when I choose epsilon smaller and smaller, n will become larger and larger. Can someone please help me?
If you recognize that:
1. The sequence is monotone decreasing.
and
2. That it shrinks quite rapidly
guess and check is really fast.
For example, I could just try n=1, n=10, then n=100 and so on. Since the sequence is monotone, if the n'th term is inside epsilon, all the following terms are also inside epsilon, and you don't have to find the smallest n, just one that works.

Arnildo already showed that for [tex]n>2[/tex], [tex]\frac{2^{\frac{n}{2}}}{2^n} > \frac{n}{2^n}[/tex]
But [tex]\frac{2^{\frac{2}{n}}}{2^n}=\frac{1}{2^{\frac{n}{2}}}[/tex]
which you can easily use to get a floor for [tex]n_\epsilon[/tex]
 
Last edited:
  • #17
1,235
1
yes but i need to find N1, N2, and N3 such that n> N1, n> N2, n > N3. This means that I need to find nuumbers N1, N2, and N3 such that any number greater than these numbers satisfies the inequality. Thus I cannot choose 'any number.' For example with the problem above, the answers are 6, 10, 14 respectively (1/10, 1/100, 1/1000). You notice that for each of these numbers is a lower bound. I would I find this.

Again thanks a lot everyone!
 
  • #18
1,235
1
Does this involve finding Bounds?

Would guess and check still be the best way to go. In Courant's book it says to "find" the numbers. Does that mean that you should guess and check?

Thanks
 

Related Threads on (n )/(2 ^n ) sequence limit problem

  • Last Post
Replies
13
Views
2K
Replies
2
Views
2K
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
730
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
3
Views
1K
Top