# filling a square of length $2^n$

suppose you have a square like this(ignore the top black border) of lenght $2^n$ and hence area $4^n$

we have to prove by Principle of Mathematical Induction that we can fill this square (well, one small box is already filled!) by the below figure

-
What have you tried? –  Chris Eagle Oct 10 '12 at 13:12
You haven't said anything in general about where the filled-in square is. Always the fifth in the top row? Always on the top row somewhere? Or what? –  Chris Eagle Oct 10 '12 at 13:13

It is a well-known and pretty tricky problem. Call $L_n$ the shape given by the removal of a $2^n\times 2^n$ square corner from a $2^{n+1}\times 2^{n+1}$ square; $Q_n$ a $2^n\times 2^n$ square. We can show that exists a $L_0$-tiling of $Q_n$ with a square removed (any square) in this way:
• there exists a $L_0$-tiling of $L_1$, so there exists a $L_n$-tiling of $L_{n+1}$, so there exists a $L_0$-tiling of $L_n$;
• $Q_{n+1}$ with a square removed can be decomposed into a $L_n$, a $L_{n-1}$, $\ldots$, a $L_1$ and a $L_0$.
Hint: can you see how to make a $2 \times 2$ square? Then can you make a replica of your piece, but twice as large?