I came across this answer to this question: Closed form expression for $n_j$ defined by $n_j=\lceil n_{j-1}/b \rceil$

I was hoping someone could clarify the following step:

$q−1 \leqslant \dfrac{(P−1)}{b} < \dfrac{x}{ab} ⩽ \dfrac{P}{b} ⩽ q $,

which says

$\left\lceil\dfrac{x}{ab}\right\rceil = > \left\lceil\dfrac{1}{b}\left\lceil\dfrac{x}{a}\right\rceil\right\rceil $.

I realize that the inequality is bounded between q-1 and q, so intuitively the ceiling equality makes sense. Testing real examples also shows that the equality is true. However, I'm a bit lost on how this is rigorously shown from the inequality. Any help would be very much appreciated!


That's exactly the same thing Daniel Fischer did in the first inequality of the answer you are asking about, just with different numbers.

Consider a real number $\alpha$. Then by definition $\lceil \alpha \rceil$ is the smallest integer greater than or equal to $\alpha$. In other words, $n = \lceil \alpha \rceil$ if and only if $n$ is an integer and $$ n - 1 < \alpha \leq n. $$ Now, the inequality you have tells you that $$ \color{red}{q-1} \color{gray}{\leq \frac{P-1}{b}} \color{red}{\pmb{<} \frac{x}{ab}} \color{gray}{\leq \frac{P}{b}} \color{red}{\leq q} $$ hence $$ q = \left\lceil\frac{x}{ab}\right\rceil. $$ On the other hand, the same inequality also tells you that $$ \color{green}{q-1} \color{gray}{\leq \frac{P-1}{b}} \color{green}{\pmb{<}} \color{gray}{\frac{x}{ab} \leq} \color{green}{\frac{P}{b} \leq q} $$ and since by definition $P = \left\lceil\frac{x}{a}\right\rceil$ we conclude that $$ q = \left\lceil\frac{P}{b}\right\rceil = \left\lceil \frac{1}{b} \left\lceil\frac{x}{a} \right\rceil \right\rceil. $$

| cite | improve this answer | |
  • $\begingroup$ Thanks a lot for breaking this down. I really appreciate it. $\endgroup$ – lstbl Dec 29 '15 at 22:14

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.