L-shaped trominoes

Use Math Induction to prove that any checkerboard with dimensions 2 x 3n can be completely covered by L-shaped trominoes for any integer n $\ge$ 1.

How do I go about proving a problem like this? I know the P(n) for this proof is the sentence "A checkerboard with dimensions 2 x 3n for any integer n $\ge$ 1. And I know P(1) is the basis, but how do I prove it fully? I honestly don't understand what we are trying to prove.

2 Answers

The problem is to prove that L shaped tronimos can always cover a board of size $2$ x $3n$ with induction. The first step, as you figured out, is the inductive base case, to show that L tronimos can cover a board of size $2$ x $3$.

This is the simplest solution for $n=1$.

The next step is to assume the problem is true for any large $N$, and then show how that implies it is true for $N+1$

Here we have a board of size $2$ x $3n$, marked blue to show that it is already covered in L tronimos. Then we consider the the board of size $2$ x $3(n+1)$, which is equivalent to $2$ x $3n + 3$, so like @Andre Nicolas said, you simply tack on another $2$ x $3$.

We now show it is possible to cover this new board with L tronimos.

That concludes the proof. It is always possible to cover a board of size $2$ x $3n$ with L tronimos.

Hint: Draw a picture. For the base case, you need to show that a $2\times 3$ can be so covered. It turns out that this is also all that is needed for the induction step.

In the induction step, note that a $2\times 3(n+1)$ checkerboard is just a $2\times 3n$ checkerboard, with a $2\times 3$ tacked on at the end.