I'm new to proof by induction and found this: A Take-Away Game.
"Consider the following game: there are $n$ chips on the table. You are challenged by your arch-enemy to play the following game: you both have to alternate moves, where in each move, you can take away either 1, 2, or 3 chips from the table. The person who has no more chips to remove from the table chips loses."
It's very similar to the proof found here: Variation of Nim: Player who takes last match loses...except player who takes last match wins.
Although I understand what is being said/explained in the proof on the first page, I'm not sure it's shown mathematically (like it is in the second link)?
For example, it says by inductive hypothesis - but I'm not sure what that would be? Is it $k=4a+b$? and why does this verify, mathematically, that the first player wins if n is not a multiple of 4? Would it be better explained using $n=0$(mod 4), and so on?
I'm trying to combine the two proofs from the links above to make a nice, easy to follow proof...but I'm coming up short.
Here is what I have so far:
n=4a+b $\forall n \in \mathbb{N}$ where $a, b \in \mathbb{Z}$ and $b = \{0, 1, 2, 3\}.$
The first player will win if and only if $n \ne 4a$.
Base:
The first player wins if and only if $n \not\equiv 0$ (mod 4).
Let $n=0$
$n=4 \cdot 0 +0 = 4.$
The first player can pick up 1- 4 chips, and second player can pick up 1, 2 or 3 chips respectively (whatever is leftover), and the second player would win.
Let $n=1$
$n=4 \cdot 0 +1 = 1.$
The first player wins by picking up all of the chips.
Let $n=2$
$n=4 \cdot 0 +2 = 2.$
The first player wins by picking up all of the chips.
Let $n=3$
$n=4 \cdot 0 +3 = 3.$
The first player wins by picking up all of the chips.
Hypothesis-
Assume that in a game with $k$ or fewer matches, the first player will win for all $b=1,2,3$ such that $i \nmid 4$, and lose for all $b=0$ such that $i \mid 4$, $\forall i \in \mathbb{N}$, $0 \le i \le k$ for some $k \in \mathbb{N}$ such that $k \ge 3$.
Conclusion-
Suppose we have a game with $k+1$ matches with $k \ge 3$, therefore $k+1 \ge 4$.
If $k+1 = 4a+1$, the first player can pick up 1 chip, leaving $k=4a$ chips for the second player. By the inductive hypothesis, the first player will win.
**This is where I don't know where to go, because from here I'm left with:
If $k+1 = 4a+ 2$, the first player picks up 2 chips, leaving $k=4a-1$ sticks for the second player...
You are claiming that Alice, the first player, wins if the pile is $1,2,$ or $3 \pmod 4$ and Bob, the second player, wins if the pile is $0 \pmod 4$. your base case is that $0$ matches are a second player win (because Bob just took the last match) and $1$ to $3$ matches are a first player win (because Alice takes them all). Then your induction says suppose we have verified it up through $k$ where $k \ge 3$. Then we want to verify it for $k+1$. If $k+1 \equiv 0 \pmod 4$, Bob wins by taking $4$ less whatever Alice takes and getting to $k-3 \equiv 0 \pmod 4$ which we know is a win for him. Otherwise, Alice takes $k+1 \pmod 4$ and gets to a second player win.
It is easier to use the language of $P$ positions and $N$ positions from the Sprague-Grundy theorem for impartial games.