2
$\begingroup$

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

1 Answers 1

6

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

$$\frac{x}{mn}\le\ell<\frac{k}n$$

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

  • 0
    I like it! Thanks!2012-11-09
  • 0
    @Maria: You’re welcome!2012-11-09
  • 0
    @DAS: Try $x=1$, $m=2$, and $n=-1$.2015-06-18
  • 0
    I see, I see. Thanks.2015-06-18
  • 0
    @DAS: You're welcome.2015-06-18