A Classic: Fix a positive integer $n$. Show that it is possible to tile any $2^n \times 2^n$ grid with exactly one square removed using 'L'-shaped tiles of three squares.
It serves as a wonderful introductory example to proof by induction. Indeed, the proof can almost be represented with two appropriate figures. Yet, for those just learning induction, it is a significant problem where the application of the inductive hypothesis is far from obvious.
