# Generalized case of Josephus Problem

I am working through the generalization of Josephus problem in "Concrete mathematics". Whereas I understood all the steps before, I am currently stuck at this point:

On the 14 page of the book the author states the recurrence defined as such:

$$J(1) = 1;$$ $$J(2n) = 2J(n) - 1;$$ $$J(2n + 1) = 2J(n) + 1$$

He then derives a more closed form 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$$

The author defines three generalized 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$$

Where do the formulas for last two come from? The author does not give a clear explanation of induction proof, rather it checks it through the special cases. I seek understanding how do we come up with this expressions.

• As J(n) is not a statement, J(n) implies (a,b,c) = (1,-1,1) is mathematical gibberish. Commented Jun 22, 2020 at 16:36
• @WilliamElliot: In this case, however, it is easily interpretable gibberish: when $f=J$, $\langle\alpha,\beta,\gamma\rangle=\langle 1,-1,1\rangle$. Commented Jun 22, 2020 at 18:17

Initially the formulas for $$A(n),B(n)$$, and $$C(n)$$ are conjectures derived from Table (1.12) near the foot of page 13: by inspection it appears that $$A(n)=2^m$$, $$B(n)=2^m-1-\ell$$, and $$C(n)=1$$, where $$n=2^m+\ell$$ and $$0\le\ell<2^m$$. (The table itself was produced by direct calculation using (1.11).)

As the authors point out, this conjecture can be proved by induction, but it’s a bit messy; it really is easier to take a different approach. The key point to bear in mind is that the functions $$A(n),B(n)$$, and $$C(n)$$ are completely determined by (1.11), independent of the values of the parameters $$\alpha,\beta$$, and $$\gamma$$. There is a whole family $$\mathscr{F}$$ of functions $$f(n)$$ defined from them by $$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma\;,\tag{1}$$ one for each choice of $$\langle\alpha,\beta,\gamma\rangle$$. We can use any choice of these parameters and associated function $$f$$ to extract information about the functions $$A(n),B(n)$$, and $$C(n)$$.

In this case we start by guessing that the constant function $$f(n)=1$$ is a member of the family $$\mathscr{F}$$. In order for that to be the case, there must be parameters $$\alpha,\beta$$, and $$\gamma$$ such that

\begin{align*} 1&=\alpha\\ 1&=2\cdot 1+\beta\\ 1&=2\cdot 1+\gamma\;; \end{align*}

this is simply substituting the function $$f(n)=1$$ into (1.11). These show that if we set $$\alpha=1$$, $$\beta=-1$$, and $$\gamma=-1$$ in $$(1)$$, we get the function $$f(n)=1$$. In other words, for all $$n$$ we have $$1=A(n)-B(n)-C(n)$$. This is a fact about the functions $$A(n),B(n)$$, and $$C(n)$$; we discovered it by looking at a particular function $$f(n)$$ and discovering that it is the member of $$\mathscr{F}$$ obtained when we set $$\langle\alpha,\beta,\gamma\rangle=\langle 1,-1,-1\rangle$$, but it is necessarily true for every choice of parameter values, because the functions $$A(n),B(n)$$, and $$C(n)$$ are independent of the parameter values: they are determined strictly by the recurrence (1.11).

Then we guess (or at any rate hope!) that the identity function $$f(n)=n$$ belongs to $$\mathscr{F}$$. Substituting that function into (1.11), we see that this would require that

\begin{align*} 1&=\alpha\\ 2n&=2\cdot n+\beta\\ 2n+1&=2\cdot n+\gamma\;, \end{align*}

and setting $$\langle\alpha,\beta,\gamma\rangle=\langle 1,0,1\rangle$$ clearly makes this true for all $$n$$. This implies that $$n=A(n)+C(n)$$ for all $$n$$.

If we knew $$A(n)$$, we could now solve for $$B(n)$$ and $$C(n)$$. Here it’s easier to start with parameter values that let us focus entirely on $$\alpha$$ than to guess another member of $$\mathscr{F}$$. If we set $$\alpha=1$$ and $$\beta=\gamma=0$$, (1.11) becomes

\begin{align*} f(1)&=1\\ f(2n)&=2f(n)\\ f(2n+1)&=2f(n)\;. \end{align*}\tag{2}

This function $$f(n)$$ isn’t a nice polynomial in $$n$$, but by our choice of parameters we know that it is $$f(n)=A(n)$$, we already suspect that $$A(n)=2^m$$, where $$2^m\le n<2^{m+1}$$, and $$(2)$$ is simple enough that it seems reasonable to try to prove by induction that $$A(n)=f(n)=2^m$$.

This is certainly true for $$n=1$$: in that case $$m=0$$, and $$2^0=1=f(1)$$. Suppose that $$f(n)=2^m$$ for all $$n$$ such that $$2^m\le n<2^{m+1}$$. If $$2^{m+1}\le k<2^{m+2}$$, let $$n=\left\lfloor\frac{k}2\right\rfloor$$; then $$k=2n$$ or $$k=2n+1$$, depending on whether $$k$$ is even or odd, and $$2^m\le n<2^{m-1}$$, so by $$(2)$$ $$f(k)=2f(n)=2\cdot2^m=2^{m+1}$$. That is, if $$f(n)=2^m$$ whenever $$2^m\le n<2^{m+1}$$, then $$f(n)=2^{m+1}$$ whenever $$2^{m+1}\le n<2^{m+2}$$, and the desired result follows by induction. If you want an explicit formula for $$m$$, note that $$2^m\le n<2^{m+1}$$ iff $$m\le\log_2n iff $$m=\lfloor\log_2n\rfloor$$. Thus, we now know that $$A(n)=2^{\lfloor\log_2n\rfloor}$$.

Then $$C(n)=n-A(n)=n-2^{\lfloor\log_2n\rfloor}$$; if $$n=2^m+\ell$$, where $$0\le\ell<2^m$$, this is simply $$C(n)=\ell$$. And $$B(n)=A(n)-C(n)-1=2^{\lfloor\log_2n\rfloor}-(n-2^{\lfloor\log_2n\rfloor})-1=2^m-\ell-1\;.$$

You might wonder what happens if we try to use a function $$f(n)$$ that isn’t in $$\mathscr{F}$$ to get information about $$A(n),B(n)$$, and $$C(n)$$. The answer is that we won’t be able to find parameters $$\alpha,\beta$$, and $$\gamma$$ consistent with $$f(n)$$. For example, if you try $$f(n)=n^2$$, you find that (1.11) becomes

\begin{align*} 1&=\alpha\\ (2n)^2&=2n^2+\beta\\ (2n+1)^2&=2n^2+\gamma\;, \end{align*}

and this is impossible: there is no constant $$\beta$$ such that $$4n^2=2n^2+\beta$$ for every $$n\ge 1$$. We see immediately that $$f(n)=n^2$$ simply isn’t in the family $$\mathscr{F}$$ of functions of the form $$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma$$ for functions $$A(n),B(n)$$, and $$C(n)$$ satisfying (1.11).