An elementary example, but pedagogically nice: a standard early induction proof example is that you can tile any $2^n \times 2^n$ square with one unit square removed, using L-shaped tiles of three unit squares each.
Surprisingly (to me), many textbooks take the base case as $n=2$. The better ones use $n=1$. But the version in The Book, though, surely starts at $n = 0$!