<s>[INST] 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.
 [/INST] So we have
$$
a_{\,n}  - 4a_{\,n - 1}  + 3a_{\,n - 2}  = 2^{\,n}  + n + 3 = q(n)
$$
and the solutions to the homogeneous equations are
$$
3^{\,n} ,\;1
$$
The homogeneous equation has constant coefficients and
$$
q(n) = 2^{\,n}  + \left( {n + 3} \right)
$$
is the sum of two terms of the form
$$
c^{\,n}  \cdot {\rm polynomial}(n)
$$
Then the theory says that in this case we can look for particular solutions of the form
$$
2^{\,n} \left( {An + B} \right),\quad C\left( {n + 3} \right)^{\,2}  + D\left( {n + 3} \right) + E
$$
(method of Undetermined Coefficients).
Since the constant term $E$ is already a homogeneous solution we can omit it and with simple passages we get
$$
A = 0,\;B =  - 4,\;C =  - 1/4,\;D =  - 1
$$
So the solution is
$$
a_{\,n}  = \alpha \,3^{\,n}  + \beta  - 4 \cdot 2^{\,n}  - {{\left( {n + 3} \right)^{\,2} } \over 4} - \left( {n + 3} \right)
$$
</s>