Notes:
1. The assumption that your conjecture is true for n = k is called the
induction hypothesis.
2. Showing that the conjecture must be true for the next
number k+1, is the rigorous check part of the principle.
3. Showing that the conjecture is true for n = 1 is the
common starting point, but it is not the only way to start. You can start with
any value of n and apply the two steps of the induction principle.
Why does the induction principle work? You
have proved the conjecture is true for n = 1 (or whatever the first value is
that you use). By showing step 2 of the induction principle, that is whenever
the conjecture is true for some integer it must also be true for the next
integer, you have established that the conjecture is true for n = 2 (or the
first value + 1). Now since it holds for n = 2, by the proof given for step 2,
it must hold for the next integer as well, so it holds for n = 3 (or the first
value + 2). Continuing in this way you have an argument that the conjecture is
true for all integers. (This suggestive argument can be made rigorous in a
variety of ways, such as by the use of the
wellordering principle.)
The Tromino Puzzle: For a square grid 2^{n}
by 2^{n} choose a single square. The rest of the grid can be tiled
using trominoes,
Lshaped tiles covering three
squares each. (Click here for pictures of
trominoes.)
Animation 1 shows the tiling on a
4 by 4 grid.
Animation 1.
Next we show how to apply the induction
principle to prove the conjecture
For a square grid 2^{n} by 2^{n}
choose a single square. The rest of the grid can be tiled using
trominoes.
Case: n = 1 For a square of side
length 2 using Figure 1 it follows that any placement of
the single white tile permits completion of the tiling by a tromino.
Figure 1.
Before proceeding to step 2 of the
induction argument, let's experiment a bit more.
Case: n = 2 Consider a square of side
length 4 which is 4 copies of a square of side length 2 as shown in Figure
2.
Figure 2.
Ideally we want to be able to prove that
if we choose any of the 16 squares, the rest can be tiled by using trominoes.
This would require 16 separate cases. Let's check a few of these to see if we
are on the right track with our conjecture.

One case is shown in Animation 1 above.

A second case can be shown in an
animation by clicking
here.

To check a few more cases click
here to use an
applet. Choose 4 for each side. You may need several tries to obtain a
tiling!

We can solve all the 16 cases. Thus we can
say
For a square grid 2^{2} by 2^{2}
choose a single square. The rest of the grid can be tiled using
trominoes.
For a square with side length 4, the 16 cases can be
done, but increasing the side length to be 2^{k} increases the number
of cases dramatically so that this strategy of "checking" all the cases is not
feasible. Let's see how to reformulate the rigorous check procedure to avoid
checking the 16 cases individually.
Starting with the 4 by 4 square in Figure 2 choose a
square to start with. It will be in one of the four 2 by 2 squares. For
instance as in Figure 3. Next place a single tromino so that it occupies one
square in each of the other three 2 by 2 squares; see Figure 4.
Figure 3. 
Figure 4. 
IMPORTANT OBSERVATION:
Now each of the four 2 by 2
squares has one square "occupied", so by the proof of the case for n = 1, it
can be tiled using (only) trominoes. It then follows that 4 by 4 square can
be tiled using (only) trominoes, once a single square has been chosen.
Thus we have proved the conjecture for the case n = 2
without considering all the cases individually. The observation above is the
key to the proof of the general case, which we do next.
This more efficient approach suggests how to carry out
the inductive process. We make the following
induction
hypothesis.
Given a positive integer k, assume that if a square grid 2^{k} by 2^{k} has one cell occupied by single square tile, then we can tile the
rest of the grid using trominoes.
Let's see how we use the induction hypothesis to prove
the conjecture for a square grid 2^{k+1} by 2^{k+1}. We start
by noting that the square grid 2^{k+1} by 2^{k+1 }is made up
of four 2^{k} by 2^{k} square grids as shown in Figure 5. We
randomly choose a single starting square in one of the quadrants of Figure 5.
We then place a single tromino so that it occupies one square in each of the
other three quadrants as shown in Figure 6. Now each of the four 2^{k} by 2^{k}
quadrants contains a single starting square.
Figure 5. 
Figure 6. 
Finally apply the induction hypothesis to
each of the four 2^{k} by 2^{k} quadrants to conclude that
For a square grid 2^{k+1} by 2^{k+1}
choose a single
square. The rest of the grid can be tiled using
trominoes.
The two
steps of the principle of induction have been verified, so it follows that our conjecture is true for any 2^{n} by 2^{n}
square.