Can someone check the solution to this recurrence relation? Here's the recurrence relation: $a_n = 4a_{n−1} − 3a_{n−2} + 2^n + n + 3$ with $a_0 = 1$ and $a_1 = 4$
Here's the solution:Write:
$$
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \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{1}{1 - 2 z} + \frac{z}{(1 - z)^2} + 3 \frac{1}{1 - z}
$$
This gives:
$$
\begin{align*}
A(z) &= \frac{1 - 4 z + 9 z^2 - 12 z^3 + 5 z^4}
             {1 - 8 z + 24 z^2 - 34 z^3 + 23 z^4 - 6 z^5} \\
     &= \frac{23}{8} \cdot \frac{1}{1 - 3 z}
          - \frac{1}{1 - 2 z}
          + \frac{3}{8} \cdot \frac{1}{1 - z}
          - \frac{3}{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:
$$
a_n = \frac{23}{8} \cdot 3^n
         - 2^n
         + \frac{3}{8}
         - \frac{3}{4} \cdot \binom{n + 1}{1}
         - \frac{1}{2} \cdot \binom{n + 2}{2}
    = \frac{23}{8} \cdot 3^n - 2^n + \frac{3}{8}
         - \frac{1}{6} (n^3 + 6 n^2 + 5 n)
$$
The problem is that when I check this with Wolfram, it 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 if this was an error or what..thanks!

But
    $a_{n+2}=4a_{n+1}−3a_n+2^{n+2}+(n+2)+3\,$!
