(1) Determine if it's practical to use Algorithm 8.3.12 on the following recursions, and explain why or why not. NOTE: YOU DO NOT NEED TO ACTUALLY FIND THE CLOSED FORM. (a) S(k) = S(k) + S(k - 1) + S(k -2) (b) S(k) = S(k - 1) +5 (c) S(k) = 95(k - 2) (2) Practice using Algorithm 8.3.12 by working through the Fibonacci sequence like we did in class to find a closed formula.Algorithm 8.3.12 Algorithm for Solving Homogeneous Finite Order Linear Relations. (a) Write out the characteristic equation of the relation S(k) + CiS(k - 1) + ...+ CnS(k - n) =0, which is a" + Clan-1+ . . . + Cn-10 + Cn =0. (b) Find all roots of the characteristic equation, the characteristic roots. (c) If there are n distinct characteristic roots, a1, a2, ... an, then the general solution of the recurrence relation is S(k) = bla,* + baaz* + . . . + bank. If there are fewer than n characteristic roots, then at least one root is a multiple root. If a; is a double root, then the bja,k term is replaced with (bjo + bilk) a,. In general, if a; is a root of multiplicity p, then the bja; term is replaced with (bjo + bjik + . . . + bj(p-1)kp-1) a*. (d) If n initial conditions are given, we get n linear equations in n unknowns (the bj's from Step 3) by substitution. If possible, solve these equations to determine a final form for S(k). Although this algorithm is valid for all values of n, there are limits to the size of n for which the algorithm is feasible. Using just a pencil and paper, we can always solve second-order equations. The quadratic formula for the roots of ar' + br + c =0 is -b+ vb2 - 4ac T = 2a The solutions of a + Cia + C2 =0 are then 101 - (-CitVC12 -402) and (-Ci - VC12 - 402) Although cubic and quartic formulas exist, they are too lengthy to introduce here. For this reason, the only higher-order relations (n 2 3) that you could be expected to solve by hand are ones for which there is an easy factorization of the characteristic polynomial