Take the 2-minute tour ×

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

1 Answer 1

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

Your Answer


