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.

In one of my analyses, I am trying to establish a lower bound on $j$.

I have the following set of equations:

$$u_0 = k$$

$$u_j \geq \lfloor u_{j-1}/2 \rfloor$$

Could I say, $j$ should be at least $\log\;k$ for $u_j$ to go to constant?

Clearly, that would hold if $k$ is a power of 2. But, what can I comment if $k$ is not a power of 2? Note, that I am particular about constants.


share|improve this question
You have no guarantee that $u_j$ becomes constant. $u_j=j$ satisfies your relation. –  Ross Millikan Apr 26 '11 at 18:26
Well, the question is, can this $u_j$ head to $0$ before $j$ is $\log k$? –  Anil Katti Apr 26 '11 at 18:50
You should be able to show that the lower limit for $u_j$ is the same for $[2^k,2^{k+1}-1]$ because of the floor function. –  Ross Millikan Apr 26 '11 at 18:55
Write the sequence $u_j$ in binary, and note that to go from $u_{j-1}$ to $u_j$, we only need to chop off the least significant bit of $u_{j-1}$. So the number of steps needed to go to zero is the number of bits in $k$, plus $1$. –  Srivatsan Aug 29 '11 at 12:09

Your Answer


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

Browse other questions tagged or ask your own question.