Suppose you have a checkerboard that is 2 spaces wide and n spaces tall. You have dominoes that can cover 2 spaces—either vertically or horizontally. We want to determine the number of ways to cover the board completely with dominoes.

(a) How many ways are there to cover the board for n = 1, 2, and 3?

(b) Let D_n be the number of ways to cover the n×2 checkerboard. Show that for n ≥ 2

D_n+1 = D_n + D_n-1

(c) Is D_n = F_n for all n?