# 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*

Now we want to prove the *closed-form* solution

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.