Question 4: Solving linear recurrence relations [5 points] Provide an explicit formula for each of the following sequences dened by a linear recurrence relation. You must Show your work. 1. a0 : 1, a1 : 0, and an : Sanil 7 60.1172 for all integers n 2 2. 2. [)0 : 76., b1 : *1, b2 : *3, and bn+3 : 2bn+2 +bn+1 * 2t)\" for all TL E N. Note: This easercise is not intended to be an exercise in algebra, so here are some useful facts. (a) The cubic polynomial 3:3 2:82 I + 2 has the following roots: A1 : 1, A2 : 1, and A3 : 2. (b) The unique solution of the system r+y+z:6 Iiy+22:71 r+y+4z:3 is given by a: = 5, y = 2, and z = 1. 3. d0 : 1, d1 : 4, and d\" : 4(dn_1 i dn_2) for all integers n 2 2. When the characteristic equation has a repeated root A, say repeated twice, the guess for the solution becomes (c1 + cgn)/\\" {and not ch\" + CgA\" where one of the two constants cl or c; would be redundant]