The Josephus Problem: The Closed Form Proof

Based on considerations of the Josephus problem for even and odd number of people, we have the following recurrence relation

$\begin{align*} \flushleft J(1) = 1 \ ; \\ J(2n) = 2J(n) - 1 \ , \qquad \ \ \text{for } n \ge 1 \ ; \\ J(2n + 1) = 2J(n) + 1 \ , \ \text{for } n \ge 1 \ . \end{align*}$ 1

Now we want to prove the closed-form solution

$\begin{equation*} J(2^m + l) = 2l + 1 \ , \qquad \text{for } m \ge 0 \text{ and } 0 \le l < 2^m \end{equation*}$ 2

by the induction on $m$ .

Proof

Base case. Assume $m = 0$ . Since $0 \le l < 2^m$ , then $0 \le l < 1$ and $l = 0$ . Now, by substitution,

$\begin{equation*} J(2^0 + 0) = 2 \times 0 + 1 \end{equation*}$

and

$\begin{equation*} J(1) = 1 \ , \end{equation*}$

which establishes the closed-form formula holds for the base case.

Inductive step. For the inductive step, we assume $m > 0$ and consider two cases, for odd and even $l$ . We suppose that (2) is true for an arbitrary $m$ and then show that (2) holds for $m + 1$ .

First, assume that $l$ is even. Since the sum of even numbers is even,

$\begin{equation*} 2^{m + 1} + l = 2n \ , \qquad \text{for an integer } n \ . \end{equation*}$

Then

$\begin{align*} n &= \frac{2^{m + 1} + l}{2} \\ &= 2^m + \frac{l}{2} \ . \end{align*}$

And therefore,

$\begin{alignat*}{3} J(2^{m + 1} + l) &= J(2n) && \quad \textit{\small by substitution} \\ &= 2J(n) - 1 && \quad \textit{\small by the recurrence relation} \\ &= 2J(2^m + \frac{l}{2}) - 1 && \quad \textit{\small by substitution} \\ &= 2 \times (2 \frac{l}{2} + 1) - 1 && \quad \textit{\small by the inductive hypothesis} \\ &= 2l + 2 - 1 && \quad \textit{\small by algebra} \\ &= 2l + 1 \ . \end{alignat*}$

Hence (2) holds for even $l$ .

Now we assume that $l$ is odd. Since the sum of an odd and even number is odd,

$\begin{equation*} 2^{m + 1} + l = 2n + 1 \ , \qquad \text{for an integer } n \ . \end{equation*}$

$\begin{align*} n &= \frac{2^{m + 1} + l - 1}{2} \\ &= 2^m + \frac{l - 1}{2} \ . \end{align*}$

Hence

$\begin{alignat*}{3} J(2^{m + 1} + l) &= J(2n + 1) && \quad \textit{\small by substitution} \\ &= 2J(n) + 1 && \quad \textit{\small by the recurrence relation} \\ &= 2J(2^m + \frac{l - 1}{2}) + 1 && \quad \textit{\small by substitution} \\ &= 2 \times (2 \frac{l - 1}{2} + 1) + 1 && \quad \textit{\small by the inductive hypothesis} \\ &= 2(l - 1 + 1) + 1 && \quad \textit{\small by algebra} \\ &= 2l + 1 \ . \end{alignat*}$

Therefore (2) holds for odd $l$ too.

Now let's look at the closed form solution from the marginal angle.