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.

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

During class, we were introduced to a proof that used the ceiling function. We assumed (without proof) that:

$$ \left\lceil{\frac{n}{2^i}}\right \rceil= \left\lceil{\frac{\lceil{\frac{n}{2}}\rceil}{2^{i-1}}}\right\rceil,$$

for $i \geq 1$, where $d$ is a positive integer.

I am interested in seeing how this can be proved. I don't know much about the ceiling function, other than its basic properties. I found a general result here , which says for positive integers $m$, $n$ and arbitrary real number $x$.

$$ \left\lceil{\frac{x}{mn}}\right \rceil= \left\lceil{\frac{\lceil{\frac{x}{m}}\rceil}{n}}\right\rceil,$$

share|cite|improve this question
up vote 3 down vote accepted

I’ll prove the more general result. Let $m$ and $n$ be positive integers and $x$ a real number. Let $k=\left\lceil\dfrac{x}m\right\rceil$. Then $$k-1<\frac{x}m\le k\;,$$ and hence $$\frac{k-1}n<\frac{x}{mn}\le\frac{k}n\;.$$

We want to show that $$\left\lceil{\frac{x}{mn}}\right \rceil=\left\lceil{\frac{\left\lceil{\frac{x}{m}}\right\rceil}{n}}\right\rceil=\left\lceil\frac{k}n\right\rceil\;.$$

Clearly $\left\lceil{\dfrac{x}{mn}}\right\rceil\le\left\lceil\dfrac{k}n\right\rceil$, so suppose to get a contradiction that $\left\lceil{\dfrac{x}{mn}}\right\rceil<\left\lceil\dfrac{k}n\right\rceil$. Then there must be an integer $\ell$ such that


and hence $\dfrac{x}m\le n\ell<k$. But then $k=\left\lceil\dfrac{x}m\right\rceil\le n\ell<k$, which is absurd.

share|cite|improve this answer
I like it! Thanks! – Maria Nov 9 '12 at 19:49
@Maria: You’re welcome! – Brian M. Scott Nov 9 '12 at 19:50
@DAS: Try $x=1$, $m=2$, and $n=-1$. – Brian M. Scott Jun 18 '15 at 7:48
I see, I see. Thanks. – DAS Jun 18 '15 at 7:57
@DAS: You're welcome. – Brian M. Scott Jun 18 '15 at 8:04

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.