Suppose you have a checkerboard that is 2 spaces wide and n spaces tall. You have dominoes that can cover 2 spaceseither vertically or horizon-tally. 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 n2 checkerboard. Show that for n 2

D_n+1 = D_n + D_n-1

(c) Is D_n = F_n for all n?

( Discrete Mathematics )