<s>[INST] Solve the recurrence relation $a_n = 4a_{n-1} - 3a_{n-2} + 2^n $ 
Solve the recurrence relation
$$a_n = 4a_{n-1} - 3a_{n-2} + 2^n $$
With initial conditions:
$a_1 = 1$
$a_2 = 11$

I have done similar recurrence relation problems to this, but none that were a non-homogeneous recurrence relation such as this one.
So far I have:
$$r^n = 4^{n-1} - 3^{n-2} $$
Divide both sides by $$\frac{1}{r^{n-2}}$$
Giving me this as my Auxiliary Equation:
$$ r^n -  4r + 3 = 0  $$
I then solved for the $r$ values and got $r = -4$ and $r = 1$
I am stumped from here as to where the non-homogeneous piece comes into play, any help is appreciated.
 [/INST] A general technique is to use generating functions. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write your recurrence as:
$$
a_{n + 2}
  = 4 a_{n + 1} - 3 a_n + 4 \cdot 2^n
$$
Multiply by $z^n$, sum over $n \ge 0$ and recognize some sums:
$\begin{align*}
\sum_{n \ge 0} a_{n + 2} z^n
  &= 4 \sum_{n \ge 0} a_{n + 1} z^n - 3 \sum_{n \ge 0} a_n z^n
       + 4 \sum_{n \ge 0} 2^n z^n \\
\frac{A(z) - a_0 - a_1 z}{z^2}
  &= 4 \frac{A(z) - a_0}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z} \\
\frac{A(z) - 1 - 11 z}{z^2}
  &= 4 \frac{A(z) - 1}{z} - 3 A(z) + 4 \frac{1}{1 - 2 z}
\end{align*}$
Solve for $A(z)$, as partial fractions:
$$
A(z)
  = \frac{7}{1 - 3 z} - \frac{4}{1 - 2 z} - \frac{2}{1 - z}
$$
This is just geometric series. We want:
$$ a_n = [z^n] A(z) = 7 \cdot 3^n - 4 \cdot 2^n - 2 $$
</s>