Here is my version of a nice induction problem.
You have a standard <m>8\times 8</m> checkerboard and a pair of scissors. If you only cut along the lines, you can create 21 L-shaped tiles (each made up of 3 checkerboard squares - no gluing allowed). However, doing so will leave one single square left over. Which of the original 64 squares could the extra, unused square be?
For which other sizes of checkerboard will this puzzle work, and which of those will the puzzle work the same way?