Proof a $2^n$ by $2^n$ board can be filled using L shaped trominoes and 1 monomino

Question

Suppose we have an $2^n\times 2^n$ board. Prove you can use any rotation of L shaped trominoes and a monomino to fill the board completely.

You can mix different rotations in the same tililng.

Answer 1

This is an old chestnut of combinatorial geometry. The proof is a fairly simple induction. We show that the $2^n\times 2^n$ board can be covered by trominoes except for one square.

If $n=1$, the solution is trivial.

Otherwise, assume that we can cover a $2^{n-1}\times 2^{n-1}$ board with trominoes except for one chosen square. Divide the $2^n\times 2^n$ board into four $2^{n-1}\times 2^{n-1}$ square quadrants. One quadrant contains the square we want to leave uncovered by trominoes, and by induction we can cover this quadrant, except for the one square, with trominoes.

For the remaining three quadrants, cover each of these except for one of its corners with trominoes. Rotate the three quadrants so that their uncovered corners lie together at the center of the board. These three remaining squares can then be covered with one more tromino.

I first saw this in Polyominoes by Solomon W. Golomb. it appears on page 5 of the revised edition, Princeton University Press, 1994.

Answer 2

Forgive me if what is below is ‘old hat’ or easily found on some other site. I only found this site whilst solving the similar problem: for which $n$ can an $n\times n$ square be covered without overlapping by T shapes each comprising four small squares. The fact that an nxn square can be almost covered by L shapes comprising three small squares leaving any prechosen square free is true for all $n\ge6, 3\nmid n$. A very simple proof can be found in The Mathematical Gazette of November 1999. Dr. R.B.J.T.Allenby (long retired from Leeds University,)