Show that a chessboard of size 2^n by 2^n can be tiled with L-shaped figures of 3 squares, such that only one square remains uncovered. In fact, the uncovered square may be any square — for every choice, there exists a tiling. In fact, the puzzle may be extended to 3D: Eight unit cubes make a cube with edge length two. We will call such a cube with one unit cube removed a "piece". A cube with edge length 2^n consists of (2^n)3 unit cubes. Prove that if one unit cube is removed from T, then the remaining solid can be decomposed into pieces.
Let us first visualize a tiling with the corner square uncovered.
Base case: For a board of size 2 x 2, one L-shape suffices.
Induction step: put 3 boards of size 2^n by 2^n next to each other such that their corner squares form an L-shape. Put a fourth board of size 2^n by 2^n so that the corner square of the resulting 2^(n+1) by 2^(n+1) board is in its corner. That proves the induction step.
Now, let us visualize how we can move the uncovered square to any square of our choice through a series of "rotations". Given an 2^(n+1) by 2^(n+1) board with a corner square removed, identify which of the four 2^n by 2^n boards that compose the 2^(n+1) by 2^(n+1) board contains the target square. Then rotate the 2^(n+1) by 2^(n+1) board clockwise so that the correct 2^n by 2^n board contains the uncovered square. Now, focus on the 2^n by 2^n board and rotate it appropriately, and so on.