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.
 A: 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)
$$
A: There is no point in including a constant term in the particular solution because constants are part of the solution of the homogeneous equation. Try $A_0 2^n + A_1 n^2+ A_2 n$.
This way you will conclude that the general solution is given by
$$
a_n = \alpha 3^n + \beta - 2^{n+2} -\frac 14 n^2 -\frac 52 n.
$$
Now you just need to compute $\alpha, \beta$  so that the initial conditions are satisfied.
A: 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}
