Suppose we are playing Lasker's nim and need to find and prove what the SG function is.
Lasker's nim is a game where the player can either (1) remove any number of chips from one pile as in nim, or (2) split one pile containing at least two chips into two non-empty piles (no chips are removed).
Computing the first few manually, we obtain:
x: 0 1 2 3 4 5 6 7 8 9 10 11 ...
g(x): 0 1 2 4 3 5 6 8 7 9 10 12 ...
where x is the position, and g(x) is the SG-value for that position.
Then, from that list, we can see a few patterns and obtain the SG-function:
g(4k + 1) = 4k + 1,
g(4k + 2) = 4k + 2,
g(4k + 3) = 4k + 4,
g(4k + 4) = 4k + 3
This is the SG-function. My question now is, how do we prove this using induction? Clearly, we must prove each of the four parts individually. Any help?
In fact, you do not want to prove all four parts individually; you want to prove them more-or-less together. In particular, all four rely on the fact that the set $\mathcal{G}_{4n} = \{g(x): x \leq 4n\}$ is the set $\{0, 1, \ldots 4n\}$ (in other words, that $g()$ permutes the numbers from $0$ through $4n$, for all $n$). This guarantees you that $g(4n+1)$, $g(4n+2)$, $g(4n+3)$, and $g(4n+4)$ are all greater than $4n$ — can you see why? — and from there it's just a function of finding what values greater than $4n$ can be obtained from piles of each of the given forms. For instance, from a pile of size $4n+1$ you can clearly move to positions of score $0\ldots 4n$ just by removing some number of stones; can you see why you can't move to any position of score $4n+1$ by splitting?