Concrete Mathematics - How is it that A(2n + 1) = 2A(n)? 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$?
 A: In this type of problem you start with the function defined for only one value: typically $n=1$. You then use a bootstrapping mechanism to define the function for further values of $n$.
Example 1
We could have $T(1)=5$ and $T(n+1)=3T(n)$.
This would give the sequence $T(1)=5, T(2)=15, T(3)=45, T(4)=135, ...$
In this case the sequence steps through all possible values of $n$ starting from $n=1$ and continuing forever...
Example 2
Now consider $T(1)=5$ and $T(2n)=3T(n)-2$.
This would give the sequence $T(1)=5, T(2)=13, T(4)=37, T(8)=109, ...$
In this case the sequence is limited to certain values of $n$; we have no idea what $T(3)$ or $T(5)$ or $T(6)$ might be.
We need a mechanism for "filling in the gaps", so another definition is required.
If we have $T(2n+1)=5T(n)-18$, then this would give us $T(3)=7$.
We already have $T(4)$.
$T(5)$ can be found by using $T(2 \times 2+1)=5T(2)-18=47$.
$T(6)$ can now be found by using $T(2 \times 3)=3T(3)-2=19$.
$T(7)$ can be found by using $T(2 \times 3+1)=5T(3)-18=17$.
This mechanism will now give the sequence for all values of $n$.
Your concern is about the function $A(n)$. This is defined by the system:
$A(1)=\alpha$
$A(2n)=2A(n)+\beta$
$A(2n+1)=2A(n)+\gamma$
but in the special case where $\alpha =1, \beta=0, \gamma=0$ we get:
$A(1)=1$
$A(2n)=2A(n)+0=2A(n)$
$A(2n+1)=2A(n)+0=2A(n)$
This does have the curious effect of having $A(2n)=A(2n+1)$, but this will happen whenever $\beta=\gamma$.
Consider
$A(1)=\alpha$
$A(2n)=2A(n)+\beta$
$A(2n+1)=2A(n)+\gamma$
where $\alpha =3, \beta=5, \gamma=5$
This gives
$A(1)=3$
$A(2n)=2A(n)+5$
$A(2n+1)=2A(n)+5$
The sequence will go:
$A(1)=3$
$A(2)=2 \times 3 + 5=11$
$A(3)=2 \times 3 + 5=11$
$A(4)=2 \times A(2) + 5=27$
$A(5)=2 \times A(2) + 5=27$
$A(6)=2 \times A(3) + 5=27$
$A(7)=2 \times A(3) + 5=27$
$A(8)=2 \times A(4) + 5=59$
$A(9)=2 \times A(4) + 5=59$
$A(10)=2 \times A(5) + 5=59$
$A(11)=2 \times A(5) + 5=59,...$
