Solve the recurrence relation $a_n=4a_{n-1}-3a_{n-2}+2^n$ with $a_1=1, a_2=11$ 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!
 A: 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}
$$
A: Let us look for a solution of shape $c2^n$ of the non-homogeneous equation. Substituting we get 
$$c2^n=4c2^{n-1}-3c2^{n-2}+2^n.$$
Dividing by $2^{n-2}$ we get $4c=8c-3c+4$, and now we know $c$.
Finally, we can write down the general solution of the non-homogeneous equation, and then meet the initial conditions.
A: For the non-homogeneous part of
$a_n=4a_{n-1}-3a_{n-2}+2^n
$,
I'll try
$a_n = c 2^n$.
Then
$c2^n=4c2^{n-1}-3c2^{n-2}+2^n
$
or,
dividing by $2^{n-2}$,
$4c =8c-3c+4$
or
$c=-4$.
As a check,
if $a^n = -4\,2^n
=-2^{n+2}
$,
$\begin{array}\\
4a_{n-1}-3a_{n-2}+2^n
&=-4\,2^{n+1}+3\, 2^n+2^n\\
&=2^n(-8+3+1)\\
&=-4\,2^n\\
&=a_n\\
\end{array}
$
As to how I chose this form to try,
experience.
