Show that for any n ge 1 a 2n times 2n grid with one square

Show that for any n ge 1, a 2n times 2n grid with one square removed can be completely covered with (non-overlapping) L-shaped tiles (shown below). An example in the case n = 3 is given below.

Solution

We can prove the statement using mathematical induction

Base Case: Let n = 1

Then the square will be of size 2 X 2, after removing one block of 1 X 1, we get 3 squares of 1 X 1 which can be easily covered by single L shaped tile as given in the problem

Let us assume that the hypothesis is true for (n=k) then we get

i.e. we can cover 2^(k) * 2^(k) with one square removed by using L tiles

Now we need to prove the assumption for n=k+1

Hence we will be having 2^(k+1) * 2^(k+1)

now divide the grid into 4 equal grids of size 2^(k) * 2^(k), from which the square has been removed we can fill it with L shaped till which was our assumption in the previous step

Now take the three squares and form such that the missing pieces form a L substitute an L in that place and hence we can cover the 2^(k+1) * 2^(k+1) grid.

Hence by principal of mathematical induction, we prove that 2^n * 2^n grid can be completely covered after removing one tile by using L shaped tiles