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) = ??? $$


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$.

| cite | improve this answer | |
  • $\begingroup$ Thank you! So taking the ceiling does not change the asymptotic properties of the function. $\endgroup$ – Erel Segal-Halevi Jun 17 '13 at 6:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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