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!
 A: You substituted $n+2$ instead of $n$ in your first step, but forgot to change the powers of $2$, etc. In other words, you should have
\begin{align}
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^{n+2} + (n+2) + 3 \quad a_0 = 1, a_1 = 4
\end{align}
instead of
\begin{align}
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^n + n + 3 \quad a_0 = 1, a_1 = 4
\end{align}
A: But
    $a_{n+2}=4a_{n+1}−3a_n+2^{n+2}+(n+2)+3\,$!
A: After the correction others have pointed out in your first line, you do the same z-transform/generating function stuff you did before, the only difference is now your two forcing terms are shifted by two.
\begin{align}
a_{n + 2} = 4 a_{n + 1} - 3 a_n + 2^{n+2} + (n+2) + 3 \quad a_0 = 1, a_1 = 4
\end{align}
You really only need to figure the generating functions for the following term
$$
\sum_{n=0}^{\infty} 2^{n+2} z^n = 2^2\sum_{n=0}^{\infty} 2^{n} z^n = \frac{4}{1-2z}
$$
What's left is $n+2+3=n+5$, so your last term turns into a $5$ in the denominator, while the second to last stays the same.  This gives you
$$
\frac{A(z) - a_0 - a_1 z}{z^2}
  = 4 \frac{A(z) - a_0}{z} - 3 A(z) 
        + \frac{4}{1-2z} + \frac{z}{(1 - z)^2}+ \frac{5}{1 - z}
$$
At this point, you should be able to finish of the problem the same way as before: solve for $A(z)$, expand by partial fractions, then inverse transform.  It seems that you need help with this step?  I didn't do this by hand but used Mathematica quickly:
$$
A(z) = \frac{-12 z^4+24 z^3-14 z^2+4 z-1}{(z-1)^3 (2 z-1) (3 z-1)} 
$$
$$
= -\frac{7}{4 (z-1)^2}+\frac{1}{2 (z-1)^3}+\frac{4}{2 z-1}-\frac{39}{8 (3 z-1)}-\frac{19}{8 (z-1)}
$$
This is in the same form as your second to last step, just with different coefficients.  Match them up in the function forms of $z$ and you have your final answer.
