Concrete Mathematics: Where is the cyclic shift for rewritten generalised Josephus function (1.15 and 1.16)?

Question

Summary

In equation labelled 1.16 how is the cyclic left shift happening? I.e. should the $\alpha$ not be at the end as in $(\beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0} \alpha)_2$ instead of $(\alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2$?

It seems to me that the derivation they go through (summarised below) is just giving $f((n)_2) = (n)_2$ or $f((n)_2) = (n)_{10}$ (as in the unfolding process)

Details

The original J-recurrence has, as the book describes, a magical solution via a single cyclic left shift

$$ J((b_m b_{m-1} ... b_1 b_0)_2) = (b_{m-1} ... b_1 b_0 b_m)_2\ \ \ \ \text{where}\ \ b_m = 1 $$

A reminder of our original generalised recurrence (1.11 in book)

$$ \begin{align} f(1) &= \alpha \\ f(2n) &= 2f(n) + \beta \\ f(2n + 1) &= 2f(n) + \gamma \\\ \end{align} $$

And then this rewritten as shown in 1.15

$$ \begin{align} f(1) &= \alpha \\ f(2n+j) &= 2f(n) + b_j \text{,}\ \ \ \ \ \text{for}j=0,1\ \ \ \text{and}\ \ n\geq1 \end{align} $$

Then, the recurrence is unfolded as follows

$$ \begin{align} f((b_m b_{m-1} ... b_1 b_0)_2) &= 2f((b_m b_{m-1} ... b_1)_2) + \beta_{b_0} \\ &= 4f((b_m b_{m-1} ... b_2)_2) + 2\beta_{b_1} + \beta_{b_0} \\ .\\ .\\ .\\ &=2^mf((b_m)_2) + 2^{m-1}\beta_{b_{m-1}}+ ... +2\beta_{b_1} + \beta_{b_0} \\ &=2^m\alpha + 2^{m-1}\beta_{b_{m-1}} ... +2\beta_{b_1} + \beta_{b_0} \end{align} $$

Finally the book concludes

The derivation above tells us

$$ f((b_m b_{m-1} ... b_1 b_0)_2) = \alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2 $$

I don't quite see how this results in the function being applied with the shifted result?

Answer 1

I think I've figured it out. The key phrase comes after equation 1.15

if we let $\beta_0 = \beta$ and $\beta_1 = \gamma$.

To expand on that

$$ \begin{align} \beta_0 &= 0_2 = \beta = -1 \\ \beta_1 &= 1_2 = \gamma = 1 \\ \end{align} $$

To put it in a couple of sentences: whenever we encounter a binary 0 it means we have $\beta_0$ which, in our original recurrence (and I think it still applies here), is $\beta$ and has a value of $-1$. Likewise for $\beta_1$ the value from our original recurrence is $1$.

So unrolling the recurrence from my question with a concrete number will look like

$$ \begin{align} f((101)_2) &= 2^2(1) + 2^1(-1) + 2^0(1) \\ &= 4 -2 + 1 \\ &= 3 \\ \end{align} $$

Which matches the closed form answer

$$ \begin{align} J(2^m + \ell) &= 2\ell + 1; \\ J(2^2 + 1) &= 2(1) + 1 \\ &= 3 \\ \end{align} $$

The book then identifies a compact solution

The derivation above tells us that

$f((b_m b_{m-1} ... b_1 b_0)_2) = \alpha \beta_{b_{m-1}} \beta_{b_{m-2}} ... \beta_{b_1} \beta_{b_0})_2$

So, again using the example of $5$ ($101$ in binary), we can simply apply the above rules (as $f(n)$) to each binary digit (symbolic placeholders inserted for reference)

$$ \begin{array}{l} n &= (1~~~~~~0~~~~1)_2 &= 5 \\ &\phantom{=} ~~\gamma~~~~~~\beta~~~~~\gamma \\ \hline f(n) &= (1~~~{-}1~~~~~1)_2 \\ f(n) &= {+}4~~{-}2~~{+}1 &= 3) \\ \end{array} $$