Tiling with Trominos; An Example of Proof By Induction

Tiling With Right Trominos

A right tromino is an L-shaped object formed by three squares in a grid. If we remove one square from a square grid of side 2ⁿ we can tile the rest of it using right trominos. This was proved by S. W. Golomb in 1954. Can you figure out the proof? The applet below uses a recursive algorithm based on that proof.