Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

Question

On the last page of the Josephus problem where things get really general, we're shown the pretty slick radix changing recurrence & solution 1.17 & 1.18

f(j) = a_j, for 1 <= j <= d;

f(dn + j) = cf(n) + B_j, for 0 <= j < d and n>=1;

&

f((b_mb_m-1...b₁b₀)_d) = (a_bmB_bm-1B_bm-2...B_b1B_b0)_c

but we're not shown how they are proved, only that we start in radix d and end in radix c.

How can one go about proving these, based on what has been presented thus far in the problem? Sorry for the typesetting I'm new to this.

Answer 1

The derivation of $(1.18)$ from $(1.17)$ closely follows that of $(1.16)$ from $(1.15)$. From $(1.17)$, we want to evaluate $f(dn+j)$ iteratively. We choose to write $dn+j$ using radix $d$:

$$dn+j = (b_mb_{m-1}\cdots b_1b_0)_d.$$

In applying the recursive relation in $(1.17)$ we go from $dn+j$ to $n$. In base $d$ arithmetic, this means simply a right-shift, dropping the least significant digit $b_0 = j$. Hence, we can begin to iterate recursively using $(1.17)$ and arriving at $(1.18)$:

\begin{eqnarray*} f((b_m b_{m-1}\cdots b_1b_0)_d) &=& cf((b_mb_{m-1}\cdots b_1)_d) + \beta_{b_0} \\ &=& c^2f((b_mb_{m-1}\cdots b_2)_d) + c\beta_{b_1} + \beta_{b_0} \\ &=& c^3f((b_mb_{m-1}\cdots b_3)_d) + c^2\beta_{b_2} + c\beta_{b_1} + \beta_{b_0} \\ && \cdots \\ &=& c^m f((b_m)_d) + c^{m-1}\beta_{b_{m-1}} + \cdots + c\beta_{b_1} + \beta_{b_0} \\ &=& c^m \alpha_{b_m} + c^{m-1}\beta_{b_{m-1}} + \cdots + c\beta_{b_1} + \beta_{b_0} \\ &=& (\alpha_{b_m} \beta_{b_{m-1}} \cdots \beta_{b_1} \beta_{b_0})_c \end{eqnarray*}