Prove using principle of mathematical induction

Question

The game Nim is played with two players and two piles of matches. In each turn, each player removes some non-zero number of matches from one of the two piles. The winning player is the player who removes the last match. Prove that if the piles start with equal (non-zero) numbers of matches, then the second player always has a winning strategy.

Answer 1

The base case is when both piles have $1$ match, where you can verify trivially that the second player has a winning strategy (in fact it is the only strategy). Now assume true for all pile sizes $n \leq k$, i.e. if both piles have $n \leq k$ matches, then the second player has a winning strategy. This is called strong induction.

Now consider a game where both piles have $n = k+1$ matches. The first player must take from one of the piles, say they take $a > 0$ matches. If $a = n$, then the second player simply takes all the matches in the other pile to win. Otherwise, $a < n$, then after the first player's move one pile has $n - a$ matches, and the other has $n$ matches. Then by taking $a$ matches from the pile that contains $n$ matches, the game is transformed into a game of Nim where both piles have $ 0 < n - a < n$ matches, and the original second player remains the second player in the new game. By the inductive hypothesis, the second player has a winning strategy for this game, and thus we've shown that he has a winning strategy when each pile has $k + 1$ matches.

This actually tells you what the winning strategy is: just mirror the first player's move on the pile that he did not touch that turn. Follow-up: what does this tell you about who has the winning strategy when the piles are uneven?