Solve the recurrence relation: hn = 5hn−1 − 6hn−2 − 4hn−3 + 8hn−4 with initial values h0 = 0, h1 = 1, h2 = 1, and h3 = 2 using (a) the characteristic equation method and (b) the generating function method.

(a) Suppose is a solution for this recurrence, with . Then






So we expect a general solution of the form



With , we get four equations in four unknowns:



So the particular solution to the recurrence is



(b) Let be the generating function for . Multiply both sides of the recurrence by and sum over all .









From here you would write each term as a power series (easy enough, since they're all geometric or derived from a geometric series), combine the series into one, and the solution to the recurrence will be the coefficient of , ideally matching the solution found in part (a).