This is might sound like a stupid question, and I'm pretty sure I know the answer to this question, but I'm not certain.
Anyway, on page 14 of Concrete Mathematics, the author has just finished going over the Josephus problem:
Josephus
$$ J(1) = 1;$$ $$ J(2n) = 2J(n) - 1;$$ $$ J(2n + 1) = 2J(n) + 1 $$
He then derives a more closed form (as I understand it) representation of $J(n)$, being:
$$ J(2^m + l) = 2l + 1$$
where,
$$0 \le l < 2^m; n = 2^m + l, \text{for} \space n \ge 1$$
In general, for each version of $J$, he defines three corresponding constants: $\alpha$, $\beta$, $\gamma$:
Recurrence 1.11 (as per the book)
Let $f(n)$ represent the general form of $J(n)$:
$$ f(1) = \alpha $$ $$ f(2n) = 2f(n) + \beta$$ $$ f(2n + 1) = 2f(n) + \gamma$$
Where $J(n) \implies (\alpha, \beta, \gamma) = (1, -1, 1)$
He then derives a hypothesis, which involves this form of $f(n)$:
$$f(n) = \alpha A(n) + \beta B(n) + \gamma C(n)$$
where,
$$ A(n) = 2^m$$ $$ B(n) = 2^m - 1 - l$$ $$ C(n) = l$$
So, he begins his proof by "choosing particular values and combining them"; notably, he selects the constants $(\alpha, \beta, \gamma) = (1, 0, 0)$. This implies that $f(n) = A(n)$.
The result yields the following:
$$ A(1) = 1; $$ $$ A(2n) = 2A(n), \text{for} \space n \ge 1 $$ $$ A(2n + 1) = 2A(n), \text{for} \space n \ge 1 $$
My confusion stems from the fact that, all of a sudden, we're mapping $A(2n + 1) = 2A(n)$, with a 1 getting eaten by the function...
How is it that $A(2n + 1) = A(2n) = 2A(n)$?
Are these implying that
$$ A(2n + 1) = 2A(n) + 1\gamma$$
with $\gamma = 0$?
