Answer to Question #160838 in Discrete Mathematics for eyasu

Question

solve these non-homogeneous recurrence relation an+ 4an-1 − 5an-2=n+2 where a0=1 & a1=-1

Answer 1

A solution $b_n$ to the non-homogeneous recurrence is similar to f(n).

Guess:

$b_n=cn+d$

Then:

$cn+d+4(c(n-1)+d)-5(c(n-2)+d)=n+2$

$n-4=0$

$c=d=b_n=0$

Solution of the given recurrence is

$a_n=b_n+h_n$

where $h_n$ is a solution for the associated homogeneous recurrence:

$h_n+4h_{n-1}-5h_{n-2}=0$

In our case: $a_n=h_n$

Characteristic equation:

$r^2+4r-5=0$

$r_1=\frac{-4-\sqrt{16+20}}{2}=-5, r_2=1$

$a_n=\alpha_1r_1^n+\alpha_2r_2^n$

$a_n=\alpha_1(-5)^n+\alpha_2$

$a_0=\alpha_1+\alpha_2=1$

$a_1=-5\alpha_1+\alpha_2=-1$

$-5\alpha_1+(1-\alpha_1)=-1$

$\alpha_1=1/3,\alpha_2=2/3$

Solution:

$a_n=\frac{1}{3}(-5)^n+\frac{2}{3}$