Nim Game - Mathematical Insight

The DP reveals a pattern: you win if $n \not\equiv 0 \pmod 4$. Can we prove this directly? From $n \equiv 0 \pmod 4$: any move (1, 2, or 3) leaves $n' \not\equiv 0 \pmod 4$. Opponent wins. From $n \not\equiv 0 \pmod 4$: take $n \mod 4$ stones. Leave $n' \equiv 0 \pmod 4$. Opponent loses.

This is the power of game theory DP: compute the pattern with DP, then prove and simplify to $O(1)$. This pattern appears in many game theory problems. Look for cyclic structures in the win/lose sequence.