Proof
The proof is by induction. For n = 1, the assertion is obvious. With a square removed from a 2×2 board, the remaining part is exactly an L-shaped tromino piece.
Assume the statement true for n = k-1 and let n = k. Draw the center lines of the 2k×2k board. The cut-off square lies in exactly one of the four thus obtained 2k-1×2k-1 boards. We may remove one square from each of the other three boards by placing a tromino at the center of the 2k×2k board. The result is a tromino and four 2k-1×2k-1 boards, each with a square removed - just a situation to apply the inductive hypothesis.
The proof is so simple, its first step was made into a proof without words.
Remark 1
You can test your understanding of Golomb's theorem by trying to tile the board manually.
Remark 2
We may base the last step of the proof on the fact that a tromino can be covered with 4 twice as small copies of itself which makes it a rep-4 tile (a rep-tile variety):
Thus a 2k×2k board could be looked at as combining one big piece (green) of tromino and a smaller, 2k-1×2k-1 board with a 1×1 square removed.
References
- B. Bollobás, The Art of Mathematics: Coffee Time in Memphis, Cambridge University Press, 2006, #40
- S. Golomb, Two Right Tromino Theorems, in The Changing Shape of Geometry, edited by C. Pritchard, Cambridge University Press, 2003
- R. Nelsen, Proofs Without Words II, MAA, 2000, p. 123
