Chapter 8.1, Problem 26E

a) Find a recurrence relation for the number of ways to completely cover a $2\times n$ checkerboard with $1\times 2$ dominoes. [Hint: Consider separately the coverings where the position in the top right corner of the checkerboard is covered by a domino positioned horizontally and where it is covered by a domino positioned vertically.)

b) What are the initial conditions for the recurrence relation in part (a)?

c) How many ways are there to completely cover a $2\times 17$ checkerboard with $1\times 2$ dominoes?