Give a simple and exact expression for \(n_j\) in equation (4.27) for the case in which \(b\) is a positive integer instead of an arbitrary real number.
Recall from equation (4.27) that:
\[n_j = \begin{cases} n & \text{if } j = 0 \\ \lceil n_{j-1}/b \rceil & \text{if } j > 0 \end{cases}\]When \(b\) is a positive integer, we can derive an exact closed-form expression for \(n_j\). The key insight is that when \(b\) is an integer, the ceiling operation in the recurrence has a predictable pattern. At each level \(j\), we’re dividing by \(b\) and rounding up, which is equivalent to computing \(\lceil n/b^j \rceil\).
To see this pattern, let’s consider a concrete example. Suppose \(n = 100\) and \(b = 3\):
\[\begin{align*} n_0 &= 100 \\ n_1 &= \lceil 100/3 \rceil = \lceil 33.33 \rceil = 34 \\ n_2 &= \lceil 34/3 \rceil = \lceil 11.33 \rceil = 12 \\ n_3 &= \lceil 12/3 \rceil = 4 \end{align*}\]Notice that \(n_2 = 12 = \lceil 100/3^2 \rceil\), and \(n_3 = 4 = \lceil 100/3^3 \rceil\). This suggests the pattern \(n_j = \lceil n/b^j \rceil\).
Let’s prove this formally by working through the algebraic derivation:
\[\begin{align*} n_0 &= n \\ n_1 &= \lceil n/b \rceil \\ n_2 &= \lceil n_1/b \rceil = \lceil \lceil n/b \rceil / b \rceil \end{align*}\]For integer \(b\), we can simplify the nested ceiling operations. The key observation is that:
\[\lceil \lceil n/b \rceil / b \rceil = \lceil n/b^2 \rceil\]This can be proven by induction. More generally, we claim that:
\[n_j = \lceil n/b^j \rceil\]Proof by induction:
Base case: For \(j = 0\), we have \(n_0 = n = \lceil n/b^0 \rceil = \lceil n/1 \rceil\).
Inductive step: Assume \(n_k = \lceil n/b^k \rceil\) for some \(k \geq 0\). We need to show that \(n_{k+1} = \lceil n/b^{k+1} \rceil\).
By the recurrence definition:
\[n_{k+1} = \lceil n_k/b \rceil = \lceil \lceil n/b^k \rceil / b \rceil\]For positive integers \(b\) and any real \(x\), we have:
\[\lceil \lceil x \rceil / b \rceil = \lceil x/b \rceil\]This is because \(\lceil x \rceil\) is the smallest integer greater than or equal to \(x\), so dividing by \(b\) and taking the ceiling again gives the same result as dividing \(x\) by \(b\) directly and taking the ceiling.
Therefore:
\[n_{k+1} = \lceil n/b^{k+1} \rceil\]
When \(b\) is a positive integer, the exact expression for \(n_j\) is:
\[n_j = \left\lceil \frac{n}{b^j} \right\rceil\]This closed-form expression is much simpler than the recursive definition and makes it easy to compute \(n_j\) for any value of \(j\) directly, without needing to compute all intermediate values. For our example with \(n = 100\) and \(b = 3\), we can now instantly verify: \(n_2 = \lceil 100/9 \rceil = 12\) and \(n_4 = \lceil 100/81 \rceil = 2\).