(a) Suppose [tex]h_n=r^n[/tex] is a solution for this recurrence, with [tex]r\neq0[/tex]. Then
[tex]r^n=5r^{n-1}-6r^{n-2}-4r^{n-3}+8r^{n-4}[/tex]
[tex]\implies1=\dfrac5r-\dfrac6{r^2}-\dfrac4{r^3}+\dfrac8{r^4}[/tex]
[tex]\implies r^4-5r^3+6r^2+4r-8=0[/tex]
[tex]\implies (r-2)^3(r+1)=0\implies r=2,r=-1[/tex]
So we expect a general solution of the form
[tex]h_n=c_1(-1)^n+(c_2+c_3n+c_4n^2)2^n[/tex]
With [tex]h_0=0,h_1=1,h_2=1,h_3=2[/tex], we get four equations in four unknowns:
[tex]\begin{cases}c_1+c_2=0\\-c_1+2c_2+2c_3+2c_4=1\\c_1+4c_2+8c_3+16c_4=1\\-c_1+8c_2+24c_3+72c_4=2\end{cases}\implies c_1=-\dfrac8{27},c_2=\dfrac8{27},c_3=\dfrac7{72},c_4=-\dfrac1{24}[/tex]
So the particular solution to the recurrence is
[tex]h_n=-\dfrac8{27}(-1)^n+\left(\dfrac8{27}+\dfrac{7n}{72}-\dfrac{n^2}{24}\right)2^n[/tex]
(b) Let [tex]G(x)=\displaystyle\sum_{n\ge0}h_nx^n[/tex] be the generating function for [tex]h_n[/tex]. Multiply both sides of the recurrence by [tex]x^n[/tex] and sum over all [tex]n\ge4[/tex].
[tex]\displaystyle\sum_{n\ge4}h_nx^n=5\sum_{n\ge4}h_{n-1}x^n-6\sum_{n\ge4}h_{n-2}x^n-4\sum_{n\ge4}h_{n-3}x^n+8\sum_{n\ge4}h_{n-4}x^n[/tex]
[tex]\displaystyle\sum_{n\ge4}h_nx^n=5x\sum_{n\ge3}h_nx^n-6x^2\sum_{n\ge2}h_nx^n-4x^3\sum_{n\ge1}h_nx^n+8x^4\sum_{n\ge0}h_nx^n[/tex]
[tex]G(x)-h_0-h_1x-h_2x^2-h_3x^3=5x(G(x)-h_0-h_1x-h_2x^2)-6x^2(G(x)-h_0-h_1x)-4x^3(G(x)-h_0)+8x^4G(x)[/tex]
[tex]G(x)-x-x^2-2x^3=5x(G(x)-x-x^2)-6x^2(G(x)-x)-4x^3G(x)+8x^4G(x)[/tex]
[tex](1-5x+6x^2+4x^3-8x^4)G(x)=x-4x^2+3x^3[/tex]
[tex]G(x)=\dfrac{x-4x^2+3x^3}{1-5x+6x^2+4x^3-8x^4}[/tex]
[tex]G(x)=\dfrac{17}{108}\dfrac1{1-2x}+\dfrac29\dfrac1{(1-2x)^2}-\dfrac1{12}\dfrac1{(1-2x)^3}-\dfrac8{27}\dfrac1{1+x}[/tex]
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 [tex]x^n[/tex], ideally matching the solution found in part (a).
