<s>[INST] Finding this solution to a recurrence relation So, I know that the recurrence relation $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$ has the solution of $a_n = -4(2^n) - n^2 / 4 - 5n / 2 + 1/8 + (39/8)(3^n)$.  I just wanted to know how we arrived at this solution.  Thank you!
 [/INST] Write:
$$
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 4 \cdot 2^n + n + 5 \quad a_0 = 1, a_1 = 4
$$
Define $A(z) = \sum_{n \ge 0} a_n z^n$. If you multiply the recurrence by $z^n$ and sum over $n \ge 0$ you get:
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = 4 \frac{A(z) - a_0}{z} - 3 A(z) 
        + \frac{4}{1 - 2 z} + \frac{z}{(1 - z)^2} + 5 \frac{1}{1 - z}
$$
This gives:
$$
\begin{align*}
A(z) &= \frac{1 - 4 z + 14 z^2 - 24 z^3 + 12 z^4}
             {1 - 8 z + 24 z^2 - 34 z^3 + 23 z^4 - 6 z^5} \\
     &= \frac{39}{8} \cdot \frac{1}{1 - 3 z}
          - 4 \cdot \frac{1}{1 - 2 z}
          + \frac{19}{8} \cdot \frac{1}{1 - z}
          - \frac{7}{4} \cdot \frac{1}{(1 - z)^2}
          - \frac{1}{2} \cdot \frac{1}{(1 - z)^3}
\end{align*}
$$
Expanding the geometric series, and also:
$$
(1 - z)^{-k} = \sum_{n \ge 0} (-1)^n \binom{-k}{n} z^n
          = \sum_{n \ge 0} \binom{n + k - 1}{k - 1} z^n
$$
gives:
$$
\begin{align*}
a_n &= \frac{39}{8} \cdot 3^n
         - 4 \cdot 2^n
         + \frac{19}{8}
         - \frac{7}{4} \cdot \binom{n + 1}{1}
         - \frac{1}{2} \cdot \binom{n + 2}{2} \\
    &= \frac{39}{8} \cdot 3^n - 4 \cdot 2^n
         - \frac{1}{8} (2 n^2 + 20 n - 1)
\end{align*}
$$
</s>