(d) Tiling boards (i) Find a recurrence relation and initial conditions for the number of ways to completely cover a 2 x n checkerboard with 1 x 2 dominoes. For example, if 3, one solution is 2 x 3 checkerboard: covered with 3 dominoes: shorthand for same solution 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.] (ii) Check your answer for n 4 by iteratively using your recurrence relation, and by counting the number of these sequences by hand. (iii) How many ways are there to completely cover a 2 6 checkerboard with 1 x 2 dominoes