Question

Let Dn denote the number of ways to cover the squares of a 2-by-n board using plain dominos. Then it is easy to see that D1 = 1, D2= 2, and D3 = 3. Compute a few more values of Dn and guess an expression for the value of Dn and use induction to prove you are right.

Answer 1

See explanation below.

Explanation:

The area of a plain domino equal the area of a 2-by-1 board, so it is easy to see that D4=4, D5=5, and so on.

Let's prove by induction than Dn=n for every natural number n.

1) Obviously, D1 is true.

2) Assume now that Dn is true for a given natural n, that is to say, a 2-by-n board can be covered with n dominoes.

we must prove that this implies D(n+1) is also true.

But the area of a 2-by-(n+1) board equals the area of a 2-by-n board plus the area of a 2-by-1 board.

By 2), we can cover the 2-by-n board with n dominoes and by 1) we can cover the 2-by-1 board with 1 domino, so we just need n+1 dominoes to cover the 2-by-(n+1) board, which is what we wanted to prove.