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.
Best Answer
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<m+1$ 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).