Two Geometric Mathematical Induction Proofs

Proof by mathematical induction is a powerful weapon in the mathematician's arsenal, but I confess that I don't care too much for this type of proof. Proofs by mathematical induction typically don't shed light on why the result is true or how it might have been discovered in the first place.

When I recently gave a two-hour workshop for high school teachers on using mathematical induction, I looked around for some easy but somewhat unusual examples. The two that I found that were proofs of geometrical results turned out to be the students' favorites. I present them here. Actually, I am stating the problems and will give a link to the proofs so that you can try to come up with the proof for yourself.

The two-color map theorem
A number of straight lines are drawn in the plane, dividing it into regions. Show that each region may be colored either red or black in such a way that no two neighboring regions have the same color. Solution is here.

Tiling with trominoes
Given an n x n chessboard where n is a positive power of two, with one corner square removed, prove that it can be tiled with trominoes. (A tromino is a figure that can exactly cover 3 contiguous squares, not all in in the same rank or file.) Solution is here.