Concrete Mathematics: Where is the cyclic shift for rewritten generalised Josephus function (1.15 and 1.16)? 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?
 A: 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}
$$
