Strong induction:
  Nim (one pile of pebbles, a move means remove 1-3;
       last player to move loses (as they spoil the fun).)
  Show: If remainder(n,4)=1, then player 2 has a forced win.
  Corollary: in all other cases, player 1 has a forced win.

  [Got to here]

--------------
Looking back on this solution:
(arguably) base cases of n=1,n=2,n=3, and n=4 pebbles were needed
so that the inductive step could use P(k-4).

In general (esp. for strong induction), you
can show several base cases (say, kappa of them),
and then separately in induction that for all k >= kappa,
  P(1)...P(k) --> P(k+1)
  (where presumably this argument needs to use P(k+1-kappa),
  which is why you needed to have k+1-kappa > 0.)



A subtle note of caution
Note that when P(n) is a statement of the form
  "For all [Nifty] sets if size n, then [Blah]",
when showing (say) P(5), we start with
  "Given an arbitrary [Nifty] set {a_1, ..., a_5},
   we'll show that this set has [Blah]".
We do *not* say "we start with a [Nifty] set of size 4,
and add one more element to it to create a [Nifty] set
of size 5".
This reason is, while your proof talks about [Nifty] sets
of size 5 constructed in the way you saw fit,
it might *not* be talking about *all* [Nifty] sets of size 5.