RtW

10 April 2022

# 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

1

Now we want to prove the closed-form solution

2

by the induction on .

#### Proof

Base case. Assume . Since , then and . Now, by substitution,

and

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

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

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

Then

And therefore,

Hence (2) holds for even .

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

So

Hence

Therefore (2) holds for odd too.

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