# Concrete Mathematics Josephus Problem: How to prove 1.17 & 1.18

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) = aj, for 1 <= j <= d;

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

&

f((bmbm-1...b1b0)d) = (abmBbm-1Bbm-2...Bb1Bb0)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.

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)$: