Prove by induction that a checkerboard missing two squares can be covered by dominoes

Question

I had a lot of trouble with this induction problem from Rosen's Discrete Mathematics and Its Applications, 8th ed.:

Use mathematical induction to show that a rectangular checkerboard with an even number of cells and two squares missing, one white and one black, can be covered by dominoes.

(We can assume the board has a black-white checkerboard coloration.)

For my partial attempt, I let $ P(n, k) $ be the claim that a $ 2n \times k $ checkerboard missing a white and a black cell can be covered by dominoes. I also noted that, in order for $ P(n, k) $ to be true, we must have $ n \geq 1 $ and $ k \geq 2 $ i.e. both sides of the checkerboard must have length at least 2.

But after that, I wasn't sure what the basis and inductive steps would be. For the basis step, I proved $ P(1, 2) $ true, but I probably should've include more base cases, just didn't know which ones.

The inductive step was the hardest part for me. I was fairly certain this would be a proof by strong induction, since the inductive step probably involves splitting up a checkerboard into smaller boards. The issue here is that at least one of these smaller boards will not have a black and a white cell missing, meaning we cannot directly apply the inductive hypothesis.

I was also feeling iffy about applying induction on a proposition containing two variables, since we only learned how to do induction on propositions of one variable. But I couldn't figure out a formulation of the claim that uses only one variable and covers all cases for the dimensions of the board.

Is there a less convoluted way of going about doing this? Did I miss something obvious?

(Of course, this question is much more easily proven by a coloring argument, but it was assigned as homework in a section on induction, so we had to use that proof method.)

Answer 1

I don't know if this is enough use of induction to qualify, but you can show for boards with the even dimension at least $4$ that you can cover the board with a loop of dominoes where you follow one side and snake over the rest. You can start with $4 \times 4$ as the base case and add one column or two rows as many times as needed. An example $6 \times 5$ is shown below. Now if you remove two cells of opposite colors you leave two pieces of the path of even length, so you can cover the board with two cells removed. You can do the $2 \times n$ boards with just a loop, so you get the same result.