# 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!

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.

• Thank you for this answer! – Stefan Kanev Oct 1 '13 at 7:57
• What is q here? I did not understand, how you came up with P=q.b-r. – V K May 12 at 5:40
• @VK $q$ is $\bigl\lceil\frac{P}{b}\bigr\rceil$. Since we're dealing with $\lceil\,\cdot\,\rceil$ and not with $\lfloor\,\cdot\,\rfloor$, instead of the usual division algorithm I use the variant that for $b$ a positive integer, every integer $k$ can be uniquely written in the form $k=q\cdot b-r$ with $0\leqslant r<b$. (The usual division algorithm gives a unique representation $k=\tilde{q}\cdot b+\tilde{r}$ with $0\leqslant\tilde{r} < b$. If $\tilde{r}=0$, let $q=\tilde{q}$ and $r=\tilde{r}$. Otherwise let $q=\tilde{q}+1$ and $r=b-\tilde{r}$.) – Daniel Fischer May 12 at 11:54
• Also how did you conclude from $$q-1 \leqslant \frac{P-1}{b} < \frac{x}{ab} \leqslant \frac{P}{b} \leqslant q,$$ the result. We can only conclude that the middle three terms in that are either q,q-1 or some fraction between these. – V K May 13 at 4:21
• We have a strict inequality in the middle, so we know that $\bigl\lceil \frac{x}{ab}\bigr\rceil = \bigl\lceil \frac{P}{b}\bigr\rceil = q$, since the two fractions are stricty larger than $q-1$, and less than or equal to $q$. – Daniel Fischer May 13 at 12:07