Concrete Mathematics: Josephus Problem: Generalised table for small values of $n$

Question

I am trying to understand how table 1.12 is constructed; where they start with $f(1)=α$ and working up from there. This is in the context of trying to find a closed form of the generalised Josephus recurrences:

$f(1)=\alpha$, for $n \geqslant 1$

$f(2n)=2f(n)+\beta$, for $n \geqslant 1$

$f(2n+1)=2f(n)+\gamma$, for $n \geqslant 1$

The book then constructs the following table for small values of $n$

$$ \begin{array}{|c|lc|} \hline n& f(n) \\ \hline 1 &\ \ \alpha \\ \hline 2 & 2\alpha+\beta \\ 3 & 2\alpha\ \ \ \ \ \ \ \ \ \ \ \ +\ \ \gamma\\ \hline 4 & 4\alpha + 3\beta\\ 5 & 4\alpha + 2\beta\ \ \ +\ \ \gamma\\ 6 & 4\alpha + \ \ \beta\ \ \ +2\gamma\\ 7 & 4\alpha + \ \ \ \ \ \ \ +3\gamma\\ \hline 8 & 8\alpha + 7\beta\\ 9 & 8\alpha + 6\beta\ \ \ \ + \gamma \\ \hline \end{array} $$

Do they construct the generalised table from scratch somehow or use the existing concrete table as a stepping stone?

So far I've been using the concrete table of small values as a stepping stone to attempt to understand the generalised table. By "concrete table of small values" I mean this one

$$ \begin{array}{|c|c|} \hline n & 1 & 2\ \ 3 &4\ \ 5\ \ 6\ \ 7\ & 8\ \ 9\ \ 10\ \ 11\ \ 12\ \ 14\ \ 15 & 16 \\ \hline J(n) &1&1\ \ 3&1\ \ 3\ \ 5\ \ 7 &1\ \ 3\ \ 5\ \ 7\ \ 9\ \ 11\ \ 13\ \ 15 & 1 \\ \hline \end{array} $$

Where the output of $J(n)$ is grouped by power of two. Using the concrete table (and thus $\alpha = 1$, $\beta = -1$, and $\gamma = 1$)I think I understand why $\alpha$'s coefficient is $n$'s largest power of 2 i.e. we're just representing symbolically what the concrete table has.

Similarly for $\beta$'s coefficient decreasing: the $J(n)$ output starts small so we need a negative $\beta$ of larger magnitude at the start to get 1, then reducing the magnitude i.e. for $n=4$ to $n=7$ it is $3\beta$, $2\beta$, and $\beta$.

Then we need to start counting upwards with $\gamma$ so $J(n)$'s output increases: using example above of $n$ 4 to 7 it is $\gamma$, $2\gamma$, and $3\gamma$. It almost seems like there is some kind of "middle" that $\beta$ and $\gamma$ are relative to.

Assuming the above makes sense, is there a way to mechanically construct that generalised table without needing to refer to anything else?

Answer 1

It looks like they simply calculated those few values of $f(n)$ using the definition of $f(n)$. First of all, this is a recursive definition, so it needs an initial value to start the recursion — that's what $f(1)=\alpha$ is. Also note that the definition of $f$ tells us to use different formulas for even or for odd inputs. For example:

• $f(2)=f(2\cdot1)=2f(1)+\beta=2\alpha+\beta$;
• $f(3)=f(2\cdot1+1)=2f(1)+\gamma=2\alpha+\gamma$;
• $f(4)=f(2\cdot2)=2f(2)+\beta=2(2\alpha+\beta)+\beta=4\alpha+3\beta$;
• $f(5)=f(2\cdot2+1)=2f(2)+\gamma=2(2\alpha+\beta)+\gamma=4\alpha+2\beta+\gamma$;

and so on.

And then, after calculating a bunch of these values, one can observe certain patterns in these expression. I'd say that what happened here: they (whoever they are) observed these patterns and decided to split the table into groups to make these patterns more clearly visible to their readers. In my opinion, the next logical step would be to prove these patterns, probably by induction.