Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|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

Your Answer


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.