Question

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.

Answer 1

(a) Suppose $h_n=r^n$ is a solution for this recurrence, with $r\neq0$. Then

$r^n=5r^{n-1}-6r^{n-2}-4r^{n-3}+8r^{n-4}$
$\implies1=\dfrac5r-\dfrac6{r^2}-\dfrac4{r^3}+\dfrac8{r^4}$
$\implies r^4-5r^3+6r^2+4r-8=0$
$\implies (r-2)^3(r+1)=0\implies r=2,r=-1$

So we expect a general solution of the form

$h_n=c_1(-1)^n+(c_2+c_3n+c_4n^2)2^n$

With $h_0=0,h_1=1,h_2=1,h_3=2$, we get four equations in four unknowns:

$\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}$

So the particular solution to the recurrence is

$h_n=-\dfrac8{27}(-1)^n+\left(\dfrac8{27}+\dfrac{7n}{72}-\dfrac{n^2}{24}\right)2^n$

(b) Let $G(x)=\displaystyle\sum_{n\ge0}h_nx^n$ be the generating function for $h_n$. Multiply both sides of the recurrence by $x^n$ and sum over all $n\ge4$.

$\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$
$\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$
$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)$
$G(x)-x-x^2-2x^3=5x(G(x)-x-x^2)-6x^2(G(x)-x)-4x^3G(x)+8x^4G(x)$
$(1-5x+6x^2+4x^3-8x^4)G(x)=x-4x^2+3x^3$
$G(x)=\dfrac{x-4x^2+3x^3}{1-5x+6x^2+4x^3-8x^4}$
$G(x)=\dfrac{17}{108}\dfrac1{1-2x}+\dfrac29\dfrac1{(1-2x)^2}-\dfrac1{12}\dfrac1{(1-2x)^3}-\dfrac8{27}\dfrac1{1+x}$

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 $x^n$, ideally matching the solution found in part (a).