I understand the recursive solution to tiling a $2^n. 2^n$ chessboard with a missing square using L-shaped tiles such as these:
using the following method to divide the original problem into subproblems:
However the proof depends on the fact that a chessboard containing $2^n . 2^n - 1$ squares can be covered by the L-shaped tiles. Whereas I can see that the number of squares that in such a defective chessboard is a multiple of $3$, I can't see why it is necessarily the case that all these squares can be covered by the L-shaped tiles, regardless of the position of the missing square.
Can anyone please help me to understand what this is the case?
This is an inductive proof. The base cases are $n = 0$ which is the first image and $n = 1$ which is the next three images (the case where the missing tile is in the bottom right corner is missing - ah well.) The key to the $n \to n + 1$ step is the last image, but that can be formalized.
In particular, the $n + 1$ case can be reduced to the $n$ case by dividing the board into four quadrants, and placing a single L-shaped tile in the pictured location so as to remove a square from those three quadrants that are not already missing a square.
Each of the four quadrants can then be tiled using the inductive hypothesis.