# Stones game proof by induction

I'm struggling with proof by induction for the following game

Two players called P2 and P2 are playing a game with a starting number of stones. Player always plays first, and the two players move in alternating turns. The game's rules are as follows: In a single move, a player can remove either 2, 3, or 5 stones from the game board. If a player is unable to make a move, that player loses the game.

A player wins where the number of stones $$n$$ is $$n≥1$$, and $$n mod 7 = 0$$ or $$n mod 7 = 1$$.

For a proof by induction, I pick $$n = 0$$ as by base case (here P1 will win)

Do I need to have a second base case for $$n = 1$$, since if I choose that as the inductive step surely I'm just proving that $$2 mod 7 = 1$$ which is self-evident.

How do I express these base cases?

My attempt at the proof is as follows:

Base case.: $$n = 0$$ (is a multiple of 7) first player loses

Inductive case: Assume the theorem is true for $$n = k$$. Prove it is true for $$n = k$$

1. Show it is true for $$n = 1$$ $$1 mod 7 = 1$$ so p1 loses

2. Assume it is true for $$n = k$$ $$n mod 7 == 0$$ OR $$n mod 7 == 1$$ so p1 loses.

Clearly this is not correct!

According to the general theory of such games the set $${\mathbb N}_{\geq0}$$ of positions $$n$$ is the disjoint union $$W\cup L$$ of two sets, characterized as follows:
• If $$n\in W$$ then the next player can enforce a win;
• If $$n\in L$$ the next player cannot avoid a loss.
From these properties we can surmise that \eqalign{n\in W&\quad\Rightarrow\quad \{n-2,n-3,n-5\}\ \ {\rm contains\ an\ element\ of}\ L\ ,\cr n\in L&\quad\Rightarrow\quad \{n-2,n-3,n-5\}\subset W\ .\cr}\tag{1} Contrary to what you are writing $$0$$ and $$1$$ are losing positions. It follows that $$\{2,3,4,5,6\}\subset W$$, since from all of these numbers there is a legal move leading to $$0$$ or $$1$$. Going stepwise up using $$(1)$$ one arrives at the conjecture that all numbers $$n=7j+k$$, $$\>0\leq k\leq6$$, with $$k\in\{0,1\}$$ are in $$L$$, and all numbers $$n=7j+k$$ with $$k\in\{2,3,4,5,6\}$$ are in $$W$$.
To prove this conjecture we do not use induction on $$n$$, but on $$j$$. For $$j=0$$ we have already shown that the claim is true. I leave it to you to perform the step $$j\rightsquigarrow j+1$$.