Example 1: When $n = 100 = (1100100)_2$ our original josephus values $\alpha=1,\beta=-1,\gamma=1$ yield:
Answer:
$ n = \qquad(1\qquad 1\qquad 0\qquad 0\qquad 1 \qquad 0\qquad 0)_2\quad=\quad 100\\ f(n) = \quad(1\qquad 1\qquad {-1}\quad {-1}\quad 1 \quad {-1}\quad {-1})_2\quad\\ = +64\qquad+32\qquad-16\qquad-8\qquad+4\qquad-2\qquad-1 = 73\\ $
Question: I understand that $f(1)=1$, But Is there a mathematical explanation to how $f(0)=-1$? Or was it based on the table in the previous page where $\beta_0 = \beta = -1$ and $\beta_1 = \gamma = 1$ ?
Example 2: We are given the recurrence
$\begin{align} f(1)=34, \\ f(2) = 5, \\ f(3n) = 10f(n) + 76, & \text{for n$\ge$ 1} \\ f(3n+1) = 10f(n) - 2, & \text{for n$\ge$ 1} \\ f(3n+2) = 10f(n) + 8 & \text{for n$\ge$ 1} \end{align}$
Compute $f(19)$
Answer: $f(19) = f((201)_3) = (5\;76\;-2)_10 = 1258$
Question:
$n = (2 0 1)_3$
We know that f(2) = 5, but how can we mathematically prove that f(0) = 76 and f(1) = -2?
The point in example 2 seems to be that if $n = 3 m + a$ with $a \in \{0,1,2\}$, the recurrence tells you $f(n) = 10 f(m) + g(a)$, where $g(0) = 76$, $g(1) = -2$ and $g(2) = 8$. So $f((a_k a_{k-1} \ldots a_0)_3)$ is expressed in terms of $g(a_0), \ldots, g(a_{k-1})$ and $f(a_k)$. Thus $19 = (2 0 1)_3$ means $f(19) = 10 f((20)_3) + g(1) = 10^2 f(2) + 10 g(0) + g(1) = 100 \times 5 + 10 \times 76 -2 = 1258$.