Page 348 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 327

FIGURE 5 Tiling 2 × 2 Checkerboards with One Square Removed.

INDUCTIVESTEP: TheinductivehypothesisistheassumptionthatP(k)istrueforthepositive
k
k
integer k; that is, it is the assumption that every 2 × 2 checkerboard with one square removed
can be tiled using right triominoes. It must be shown that under the assumption of the inductive
hypothesis, P(k + 1) must also be true; that is, any 2 k+1 × 2 k+1 checkerboard with one square
removed can be tiled using right triominoes.
To see this, consider a 2 k+1 × 2 k+1 checkerboard with one square removed. Split this
k
k
checkerboard into four checkerboards of size 2 × 2 , by dividing it in half in both directions.
This is illustrated in Figure 6. No square has been removed from three of these four checker-
k
k
boards. The fourth 2 × 2 checkerboard has one square removed, so we now use the inductive
hypothesis to conclude that it can be covered by right triominoes. Now temporarily remove the
k
k
square from each of the other three 2 × 2 checkerboards that has the center of the original,
larger checkerboard as one of its corners, as shown in Figure 7. By the inductive hypothesis,
k
k
each of these three 2 × 2 checkerboards with a square removed can be tiled by right triomi-
noes. Furthermore, the three squares that were temporarily removed can be covered by one right
triomino. Hence, the entire 2 k+1 × 2 k+1 checkerboard can be tiled with right triominoes.
We have completed the basis step and the inductive step. Therefore, by mathemati-
cal induction P (n) is true for all positive integers n. This shows that we can tile every
n
n
2 × 2 checkerboard, where n is a positive integer, with one square removed, using right
triominoes. ▲

FIGURE 6 Dividing a FIGURE 7 Tiling the
2 k+1 × 2 k+1 Checkerboard into 2 k+1 × 2 k+1 Checkerboard
k
k
Four 2 × 2 Checkerboards. with One Square Removed.

Mistaken Proofs By Mathematical Induction

As with every proof method, there are many opportunities for making errors when using mathe-
matical induction. Many well-known mistaken, and often entertaining, proofs by mathematical
Consult Common Errors
in Discrete Mathematics induction of clearly false statements have been devised, as exemplified by Example 15 and
on this book’s website for Exercises 49–51. Often, it is not easy to find where the error in reasoning occurs in such mis-
more basic mistakes. taken proofs.