Unfolding of recurrence in generalization of Josephus problem I have been going through the bit-wise generalization of Josephus problem in Concrete Mathematics. And so the author came up with these relations (I do understand this part)
$$f(1) = α ;$$
$$f(2n + j) = 2f(n) + β_j ,$$
$$\text{ for } j = 0, 1 \text{ and } n \geq 1$$
this part I understand , now the unfolding of the recurrence
However, I can't understand how the unfolding happens and why do we have two and four in the beginning of the second and third equation.
\begin{align*}f(b_m b_{m−1}...b_1 b_0)_2 &= 2f(b_m b_{m−1} . . . b_1)_2+ β_{b_0}\\&=4f(b_mb_{m−1}...b_2)_2 + 2β_{b_1} + β_{b_0}\\&=
2^mf((b_m)_2) +2^{m−1}β_{b_{m−1}} + · · · +2β_{b_1}+β_{b_0}
\\&=2^mα + 2^{m−1}β_{b_{m−1}} + · · · + 2β_{b_1} + β_{b_0}\end{align*}
Can someone shed more light how to evaluate that?
 A: Note that $$(b_mb_{m-1}\ldots b_1b_0)_2=2(b_mb_{m-1}\ldots b_1)_2+b_0\;,$$ so the recurrence says that
$$\begin{align*}
f\big((b_mb_{m-1}\ldots b_1b_0)_2\big)&=f\big(2(b_mb_{m-1}\ldots b_1)_2+b_0\big)\\
&=2f\big((b_mb_{m-1}\ldots b_1)_2\big)+\beta_{b_0}\;.
\end{align*}$$
And $$(b_mb_{m-1}\ldots b_1)_2=2(b_mb_{m-1}\ldots b_2)_2+b_1\;,$$
so in similar fashion we have
$$f\big((b_mb_{m-1}\ldots b_1)_2\big)=2f\big((b_mb_{m-1}\ldots b_2)_2\big)+\beta_{b_1}$$
and hence
$$\begin{align*}
2f\big((b_mb_{m-1}\ldots b_1)_2\big)+\beta_{b_0}&=2\Big(2f\big((b_mb_{m-1}\ldots b_2)_2\big)+\beta_{b_1}\Big)+\beta_{b_0}\\
&=4f\big((b_mb_{m-1}\ldots b_2)_2\big)+2\beta_{b_1}+\beta_{b_0}\;.
\end{align*}$$
After $k$ such steps you reach
$$2^kf\big((b_mb_{m-1}\ldots b_k)_2\big)+2^{k-1}\beta_{b_{k-1}}+2^{k-2}\beta_{b_{k-2}}+\ldots+2\beta_{b_1}+\beta_{b_0}\;.$$
when $k=m$ this is
$$2^mf\big((b_m)_2\big)+2^{m-1}\beta_{b_{m-1}}+2^{m-2}\beta_{b_{m-2}}+\ldots+2\beta_{b_1}+\beta_{b_0}\;.$$
We assume that $b_m=1$, and $f(1)=\alpha$, so this reduces to
$$2^m\alpha+2^{m-1}\beta_{b_{m-1}}+2^{m-2}\beta_{b_{m-2}}+\ldots+2\beta_{b_1}+\beta_{b_0}\;.$$
