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.

If we know that:

$$a_{i+1} \leq {a_i \over 2}$$

Then we can calculate an upper bound for every n:

$$a_{n} \leq {a_0 \over 2^n}$$

But what if we keep the elements integer, by taking the ceiling:

$$a_{i+1} \leq \lceil {a_i \over 2} \rceil$$

As long as $a_i > 1$, the series is decreasing. However, the rate of decrease is slower, and the above upper bound doesn't hold. What is the best upper bound (as a function of $a_0$ and $n$) that we can find?

$$a_{n} \leq F(a_0,n) = ??? $$

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

You have $a_{i+1} \le a_i/2 + 1/2$, so $a_n \le 1 + (a_0 - 1) 2^{-n}$. This is best possible in that it is an equality if $a_0 \equiv 1 \mod 2^n$.

share|improve this answer
    
Thank you! So taking the ceiling does not change the asymptotic properties of the function. –  Erel Segal Halevi Jun 17 '13 at 6:38
add comment

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.