1 (10 points) Solve the following recurrence relation (10 points) Solve the following recurrence relation 3 (20 points) A person invests $2500 each year in a tax-sheltered annuity at 8 percent interest compound annually. The money invested, as well as the interest earned, is not subject to taxation until withdrawn from the account. Let An represent the amount at the end of n years. Find an explicit formula for An. We assume no withdrawing in the n years 4 (20 points) Suppose we can only use three kinds of tiles to cover a lxn board. One kind has 1 x l size with red color, the second kind hag I 2 size with blue color, and the third one has x 2 size with black color. Let W(n) be the number of ways to tile the lm board, n 1,2, For example, W(1)-1, W(2)-3, as shown by the following figure Blue Black (a) One way to tile a lxl board (b) Three ways to tile a 1x2 board Please find a recurrence relation for W(n) and solve it 5 (20 points) Let Sr denote the set of all n-bit strings that do not contain the pattem 00. For example, Si-[0, 1), S2-101,10, 11), S 010, 101,110, 011, 111). Let a-|S Provethat an-re+2, n = 1, 2, . . ., wherefdenotes the Fibonacci sequence. (Hint: use mathematical induction.) 6 (20 points) Given an equilateral triangle as shown in figure (a), if we draw one line parallel to each sides such that the 3 lines divide each side into 2 segments of equal length, then we will get the figure as shown in figure (b). Let us call the triangle in (a) So, the figure in (b) Si. Similarly, we can draw k lines parallel to each side such that the 3k lines divide each side into (k+l) segments of equal length. Let us call the figure S. As an example, figure (c) shows the figure S2