This is the single pile nime game where a player has to take between 1-3 coins out of the pile. I found the pattern and wrote most of the proof, but I cannot really think of a way to prove the inductive step formally. It seems like the circumstances change every time I get to congruence with 0(mod 4) and it can't be universally proven.
[Proof of one pile take away game]
Suppose there are n coins in one pile. If n is not congruent to 0(mod 4), where a is some positive integer, then the first player will always be in the winning position if the pile n is not conguent 0(mod 4). If n is congruent 0(mod 4), then Player 1 will always be in a losing position if played correctly.
{Base cases}: if n=1, 2, or 3, then the pile is not congruent with 0(mod 4). Player 1 is in a winning position, because the player can clear the pile and win. If n=4, the pile is congruent with 0(mod 4). Player 1 has to take 1-3 coins from the pile, which causes the pile n to equal 1, 2, or 3 for Player 2’s turn, and this will be a winning position for Player 2.
{Induction hypothesis}: Now suppose pile k > 3, and assume pile k congruent 0(mod 4) is a losing position for Player 1 and pile k not congruence 0(mod 4) is a winning position for Player 1.
Best Answer
Player 1 has a winning strategy if the original number of coins is not $0($mod$4)$, and player 2 has a winning strategy if the original number of coins is $0($mod$4)$.
Rather than induction, using infinite descent (which is equivalent) would be neater.
Base case: Suppose there are $1, 2$, or $3$ coins. Player one can take all of them, and he wins. If there are $4 = 0($mod$4)$ coins, player 2 wins (as you explained before).
"Inductive" (infinite descent) step: Suppose there are $k = 0($mod$4)$ coins. Now if player 1 takes $1$ coin in turn one, player 2 will take $3$ coins in turn two. It is now player 1's turn and there are again $0($mod$4)$ coins. Similarly if player 1 takes $2$ or $3$ coins, player 2 will take $2$ or $1$ coin respectively. Thus no matter how many coins player 1 takes on his first turn, he will end up with $0($mod$4)$ coins on his next turn. By the method of infinite descent, after a finite number of turns it will be player 1's turn and only $4$ coins will remain. Thus player 2 will win.
Now suppose there are $k \neq 0($mod$4)$ coins in the starting position. If $k = 1($mod$4)$, player 1 takes 1 coin. If $k = 2($mod$4)$, player 1 takes 2 coins, and if $k = 3($mod$4)$, player 1 takes 3 coins so that on player 2's first turn he has a pile with $0($mod$4)$ coins. By the same reasoning as above, after a finite number of turns, it will be player 2's turn and only $4$ coins will remain. Thus player 1 will win.