Solve the recurrence relation:
$$a_n=4a_{n-1}-3a_{n-2}+2^n$$
With initial conditions:
$$a_1=1, a_2=11$$
I know that this is a non-homogeneous recurrence relation meaning that the first step is to solve the homogeneous part:
$$r^n=4r^{n-1}-3^r{n-2}$$
$$r^2=4r-3$$
$$r^2-4r+3=0$$
$$(r-1)(r-3)=0$$
$$r=1,r=3$$
This gives us:
$$a_n=A(1)^n+B(3)^n$$
or (if the constant B absorbs A)
$$a_n=B(3)^n$$
The non-homogeneous part is where I seem to get stuck. I attempted:
$$a_n=B(3)^n+C(2)^n$$
subbing it into the original recurrence relation:
$$B(3)^n+C(2)^n= 4[B(3)^{n-1}+C(2)^{n-1}]-3[B(3)^{n-2}+C(2)^{n-2}]+2^n$$
I am a lost on where to proceed from here. Any help would be appreciated!
[Math] Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n$ with $a_1=1, a_2=11$
discrete mathematicsrecurrence-relations
Best Answer
Let $$ b_n=a_n+2^{n+2} \quad \forall n\ge 1. $$ Then $$ b_1=a_1+2^3=9,\quad b_2=a_2+2^4=27, $$ and for every $n\ge 3$ we have: \begin{eqnarray} b_n&=&4(b_{n-1}-2^{n+1})-3(b_{n-2}-2^n)+2^{n+2}+2^n\\ &=&4b_{n-1}-3b_{n-2}+(-8+3+4+1)2^n\\ &=&4b_{n-1}-3b_{n-2}. \end{eqnarray} The characteristic equation associated to the recurrence relation $$ b_n-4b_{n-1}+3b_{n-2}=0 $$ is $$ r^2-4r+3=0, $$ and its solutions are $$ r_1=1, \quad r_2=3. $$ Therefore $$ b_n=c_1+c_2\cdot3^n, $$ where $c_1$ and $c_2$ satisfy: $$ c_1+3c_2=9,\quad c_1+9c_2=27, $$ i.e. $$ c_1=0,\quad c_2=3. $$ Hence $$ a_n=b_n-2^{n+2}=3^{n+1}-2^{n+2} $$