Forget all this, use generating functions directly. Define $A(z) = \sum_{n \ge 0} a_n z^n$, write:
$$
a_{n + 2} = 4 a_{n + 1} + 4 a_n + 8 (n + 3) \cdot 2^n
$$
Multiply by $z^n$, sum over $n \ge 0$, recognize:
\begin{align}
\sum_{n \ge 0} a_{n + r} z^n
&= \frac{A(z) - a_0 - a_1 z - \ldots - a_{r - 1} z^{r - 1}}{z^r} \\
\sum_{n \ge 0} 2^n z^n
&= \frac{1}{1 - 2 z} \\
\sum_{n \ge 0} n 2^n
&= z \frac{\mathrm{d}}{\mathrm{d} z} \frac{1}{1 - 2 z} \\
&= \frac{2 z}{(1 - 2 z)^2}
\end{align}
and get:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
= 4 \frac{A(z) - a_0}{z} + 4 A(z)
+ \frac{16 z}{(1 - 2 z)^2} + \frac{3}{1 - 2 z}
$$
This gives, written as partial fractions (partially):
$$
A(z)
= \frac{1 - 2 a_0 - 2 (a_1 - 1) z}{2 (1 - 2 z^2)} +\frac{1}{2 (1 - 2 z)}
$$
The $(1 - 2 z)^{-1}$ gives rise to a $2^n$ in the solution, while you can write:
\begin{align}
\frac{1}{1 - 2 z^2}
&= \sum_{n \ge 0} 2^n z^{2 n} \\
\frac{z}{1 - 2 z^2}
&= \sum_{n \ge 0} 2^n z^{2 n + 1}
\end{align}
Thus you get expressions for even/odd indices. Or you could split that into partial fractions too, and mess with the resulting irrationals.
If you are simply interested in a particular solution, pick any easy values, like $a_0 = 0$ and $a_1 = 1$, and expand the above.
Use generating functions, as taught by Wilf in generatingfunctionology (2nd edition, Academic Press, 1994). Define:
$\begin{align*}
A(z)
&= \sum_{n \ge 0} a_n z^n
\end{align*}$
Shift the recurrence so there are no subtractions in indices, multiply by $z^n$, sum over the values of $n$ where the recurrence is valid and recognize the resulting sums; use the initial values and solve for $A(z)$:
$\begin{align*}
a_{n + 2}
&= 4 a_{n + 1} - 5 a_n + (-1)^n \\
\sum_{n \ge 0} a_{n + 2} z^n
&= 4 \sum_{n \ge 0} a_{n + 1} z^n - 5 \sum_{n \ge 0} a_n z^n
+ \sum_{n \ge 0} (-1)^n z^n \\
\frac{A(z) - a_0 - a_1 z}{z^2}
&= 4 \frac{A(z) - a_0}{z} - 5 A(z)
+ \frac{1}{1 + z} \\
A(z)
&= \frac{1 - 2 z - 2 z^2}{(1 + z) (1 - 4 z + 5 z^2)} \\
&= \frac{1}{10 (1 + z)} + \frac{9 - 25 z}{1 - 4 z + 5 z^2}
\end{align*}$
In the end, we want the coefficient of $z^n$ in this, the path is to use partial fractions and expand as geometric series (or using the binomial theorem). The problem here is that the factors of the second denominator are complex conjugates:
$\begin{align*}
\frac{9 - 25 z}{1 - 4 z + 5 z^2}
&= \frac{9 - 25 z}{(1 - (2 - i) z) (1 - (2 + i) z)} \\
&= \frac{9 - 7 i}{2 (1 - (2 - i) z)}
+ \frac{9 + 7 i}{2 (1 - (2 + i) z)}
\end{align*}$
Thus it decomposes into two complex conjugate terms:
$\begin{align*}
[z^n] \frac{9 - 25 z}{1 - 4 z + 5 z^2}
&= \frac{9 - 7 i}{2} \cdot (2 - i)^n
+ \frac{9 + 7 i}{2} \cdot (2 + i)^n
\end{align*}$
The sum is just twice the real part of, say, the first term. Write the first term in polar form:
$\begin{align*}
2 \Re\left( \frac{9 - 7 i}{2} \cdot (2 - i)^n \right)
&= 2 \Re\left( \rho_c \mathrm{e}^{i \theta_c}
\cdot \rho^n \mathrm{e}^{i n \theta} \right) \\
&= 2 \rho_c \cdot \rho^n \cdot \cos (\theta_c + n \theta)
\end{align*}$
This form of the solution is nice in that it shows directly that:
$\begin{align*}
a_n
&= \frac{1}{10} (-1)^n
+ \Theta\left( 2 \rho_c \cdot \rho^n \right) \\
&= \Theta\left( \sqrt{3}^n \right)
\end{align*}$
There certainly is a way of writing this as an algebraic expression, but it will involve assorted surds.
Best Answer
Don’t try to find a separate particular solution; just try the general solution
$$a_n=c_12^n+c_2n2^n+c_3n^22^n=(c_1+c_2n+c_3n^2)2^n\;.\tag{1}$$
You’ll need three data points in order to solve for all three constants, so calculate $a_2$ and then use $(1)$ and the known values of $a_0,a_1$, and $a_2$ to generate a system of three equations in the unknowns $c_1,c_2$, and $c_3$.