# 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$?

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,...$