A game is played by making straight lines of dominoes. Answer the questions below and provide and explanation for (c)

1. A game is played by making straight lines of dominoes. There is an unlimited supply of five kinds of dominoes: 1 1/ 1 2 2 1 13 and 3 1 . A line of dominoes is legal if it begins and ends with a l and any two adjacent domino-ends both have the same number on them. For example, the line 1 2 21 1 1 is legal, but the line 1 2 21 1 3 and the line 12 1 1 1 1 are both illegal.) For each integer n 2 1, let , be the number of legal lines of n dominoes. For example, t = 1 because 1 1 is the only legal line of one domino. (a) Write down to and a list of all the legal lines of 2 dominoes. (b) Write down to and a list of all the legal lines of 3 dominoes. (c) Find a recurrence for t, that holds for all n 2 3. Explain why your recurrence gives the correct number for to. (d) Use your recurrence to find ta