Recurrence relation $a_n = 4a_{n-1} - 3a_{n-2} + 2^n + n + 3$ with $a_{0} = 1$ and $a_{1} = 4$ This is a nonhomogeneous recurrence relation, so there is a homogeneous and a particular solution.
Homogenous:
$a_n - 4a_{n-1} + 3a_{n-2} = 0$
$r^2 - 4r + 3 = 0$
$(r - 3)(r - 1)$
$a_n^h = \alpha(3^n) + \beta(1^n)$
This is where my solution stops because I don't know how to solve the particular solution since it would be $a_n - 4a_{n-1} + 3a_{n-2} = 2^n + n + 3$ and I'm not sure what form it should be. Would it be $A_0(r^n) + A_1(n) + A_2$ where $A_n$ is a constant or not?
I've tried solving it with that form and it ended like this:
$A_0(2^n) + A_1(n) + A_2 - 4(A_0(2^{n-1}) + A_1(n-1) + A_2) + 3(A_0(2^{n-2}) + A_1(n-2) + A_2) = 2^n + n + 3$
After simplifying and dividing $2^{n-2}$:
$A_0(2^n) - 4A_0(2^{n-1}) + 3A_0(2^{n-2}) - 4 = n + 3 + 2A_1(n) + 2A_2 - 2A_1$
And that's where I stop since I don't know what to do next.
Thanks for answering.

Here's an alternative approach. Let $A(z)=\sum_{n\ge 0} a_n z^n$ be the ordinary generating function for $a_n$.  Then the recurrence relation implies that
\begin{align}
A(z) - a_0 - a_1 z 
&= \sum_{n\ge 2}\left(4a_{n-1} - 3a_{n-2} + 2^n + n + 3\right)z^n \\
&= 4z \sum_{n\ge 2} a_{n-1} z^{n-1} - 3z^2 \sum_{n\ge 2} a_{n-2} z^{n-2} + \sum_{n\ge 2} (2z)^n + z \sum_{n\ge 2} n z^{n-1} + 3\sum_{n\ge 2}z^n \\
&= 4z (A(z)-a_0)- 3z^2 A(z) + \frac{(2z)^2}{1-2z} + z\left(\frac{1}{(1-z)^2}-1\right) + \frac{3z^2}{1-z},
\end{align}
so
\begin{align}
A(z) 
&= \frac{a_0 + a_1 z -4 a_0 z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2}-z + \frac{3z^2}{1-z}}{1-4z+3z^2}\\
&= \frac{1 - z + \frac{4z^2}{1-2z} + \frac{z}{(1-z)^2} + \frac{3z^2}{1-z}}{1-4z+3z^2}\\
&= \frac{1 - 4 z + 14 z^2 - 24 z^3 + 12 z^4}{(1 - 2 z) (1 - 3 z)(1 - z)^3 } \\
&= -\frac{4}{1-2 z} + \frac{39/8}{1-3 z} + \frac{19/8}{1-z} - \frac{7/4}{(1-z)^2} - \frac{1/2}{(1-z)^3} \\
&= \sum_{n\ge 0}\left(-4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2}\right)z^n,
\end{align}
which immediately implies that
\begin{align}
a_n &= -4\cdot 2^n + \frac{39}{8}\cdot3^n + \frac{19}{8} - \frac{7}{4}\binom{n+1}{1} - \frac{1}{2}\binom{n+2}{2} \\
&= \frac{- 2^{n + 5} + 13\cdot 3^{n + 1} -2 n^2 - 20 n + 1}{8}.
\end{align}
