Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Recall the equivalence: $$m=2^k \implies k=log_2m$$ (a) Consider the sequence: $a_1=1, a_{k+1}=2a_k$ what is the smallest k for which $a_k \geq n$? Your answer should be a function of n, and you can leave it in big-O notation.

(b) Consider the sequence: $a_1=2, a_{k+1}=a_k^2$ what is the smallest k for which $a_k \geq n$? Your answer should be a function of n, and you can leave it in big-O notation.


i am totally confused about this question, can someone please walk me through this problem or give me a nudge in the right direction, (also where does the n come from?)

share|improve this question
1  
Well, the problem itself states that you are trying to come up with the answer in terms of $n$. Can you see how in each problem, $k$ depends on $n$? –  Dennis Meng Oct 2 '13 at 5:19
    
no, how do i get started on this problem? –  notamathwiz Oct 2 '13 at 6:02
1  
If you can't answer my question, you're definitely not going to be able to get started on this problem. –  Dennis Meng Oct 2 '13 at 6:03
    
does that mean we change the k to n and write our answer in terms of n? –  notamathwiz Oct 2 '13 at 6:06
    
No, you do not change $k$ to $n$, but yes, your answer is going to be in terms of $n$. –  Dennis Meng Oct 2 '13 at 6:09

1 Answer 1

$n$ is just another variable.

This is really just a compound problem: you need to break it into parts and solve the parts.

For example, one part of the first problem could be

Find a formula for the general term of the sequence given by $a_1 = 1$, $a_{u+1}=2a_u$

(I changed the dummy variable because it doesn't matter, but it might help eliminate confusion between this part and the rest of the problem)

(I say 'could be', because this is just one approach to the problem)

share|improve this answer
    
would the general sequence of the first one be $a_k=2a_{k-1}$?? –  notamathwiz Oct 2 '13 at 6:19
    
can someone please explain what n is supposed to represent –  notamathwiz Oct 2 '13 at 6:53
    
$n$ is supposed to represent $n$, the variable integer appearing on the right hand side of the equation $a_k \geq n$. –  Hurkyl Oct 2 '13 at 6:58
    
... that you're supposed to solve for $k$ in terms of $n$. (and find the minimum solution) –  Hurkyl Oct 2 '13 at 7:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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