Prove or Disprove:
For all $n$ contained in positive integers
For any single square removed from a $2^n \times 2^n$ grid, there is a unique tiling with $L$-tiles.
The word that messes with me is "unique", I know that this statement is true, as I can produce examples, however, I am not sure how to formally prove that it is true.
There is always a tiling (this is a classic induction problem you can find all over the net) ... But it need not be unique:
\begin{array}{|c|c|c|c|c|c|c|c|} \hline A&A&B&A&A&B&A&A\\ \hline A&C&B&B&A&B&B&A\\ \hline C&C&A&A&C&C&D&D\\ \hline B&B&A&B&B&C&D&A\\ \hline A&B&C&C&B&D&A&A\\ \hline A&A&X&C&D&D&B&B\\ \hline B&C&C&A&B&B&A&B\\ \hline B&B&C&A&A&B&A&A\\ \hline \end{array}
Note that there are many ways we can mirror a 2x3 rectangle consisting of 2 L-pieces, so the tiling is not unique.
Therefore, the claim that there is a unique tiling for any $n$ is false.
Use induction! Suppose the statement is true for $2^{n-1} \times 2^{n-1}$ sized grids. Now divide the $2^n$ grid into $4$ $2^{n-1}$ sized grids. $3$ will be completely full, one will have a piece taken out. Place $1$ L piece so that it covers one spot in each of the $3$ grids that are completely full. Now use the inductive hypothesis to finish the proof!
