Closed form expression for $n_j$ defined by $n_j=\lceil n_{j-1}/b \rceil$ I'm a professional programmer working through the CLRS exercises for fun and I've come across 4.6-1, where I got stuck. It asks to find a simpler expression for $n_j$ when $b$ is a positive integer (and not an arbitrary real number) in the following formula:
$$ n_j = \begin{cases}
            n                       & \text{if } j = 0,\\
            \lceil n_{j-1}/b \rceil & \text{if } j > 0.
         \end{cases}$$
I'm uncertain how to approach this. After some poking, I came up with:
$$ n_j = \lceil n / b^j \rceil $$
I did not prove this, I just guessed. I can't see why this would hold for integers, but not for reals, which makes me doubt it is the correct solution.
Any help would be appreciated!
 A: It is the correct solution - possibly with a special case $n_0 = n$ if $n$ is not an integer.
If $a$ and $b$ are positive integers, and $x$ an arbitrary real number, then we have
$$\left\lceil \frac{x}{a}\right\rceil - 1 < \frac{x}{a} \leqslant \left\lceil \frac{x}{a} \right\rceil,$$
and dividing that by $b$ yields
$$\frac{1}{b}\left(\left\lceil\frac{x}{a}\right\rceil-1\right) < \frac{x}{ab} \leqslant \frac{1}{b}\left\lceil \frac{x}{a}\right\rceil.$$
Now, $P := \left\lceil \dfrac{x}{a}\right\rceil$ is an integer, hence we can write $P = q\cdot b - r$, with an integer $0 \leqslant r < b$. Then from $P > (q-1)\cdot b$ we conclude $P-1 \geqslant (q-1)\cdot b$, and thus
$$q-1 \leqslant \frac{P-1}{b} < \frac{x}{ab} \leqslant \frac{P}{b} \leqslant q,$$
which says
$$\left\lceil \frac{x}{ab}\right\rceil = \left\lceil \frac{1}{b}\left\lceil \frac{x}{a}\right\rceil\right\rceil.$$
It should be clear that that generalises to more than two successive divisions (and to $\lfloor\,\cdot\,\rfloor$ in place of $\lceil\,\cdot\,\rceil$, but of course you can't in general mix), so indeed
$$n_j = \left\lceil\frac{n_{j-1}}{b}\right\rceil = \left\lceil \frac{1}{b}\left\lceil \frac{n}{b^{j-1}}\right\rceil\right\rceil = \left\lceil \frac{n}{b^j}\right\rceil.$$
It does not work when dividing by arbitrary (positive) real numbers, because then you cannot conclude $P-1 \geqslant (q-1)\cdot b$ from $P > (q-1)\cdot b$, you need the granularity of integers for that.
