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,$$
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<k$. But then $k=\left\lceil\dfrac{x}m\right\rceil\le n\ell<k$, which is absurd.