System of Recurrence Relations Solve the following System of Recurrence Relation:
$$a_n = 2a_{n-1} - b_{n-1} + 2, a_0 = 0$$
$$b_n = -a_{n-1} + 2b_{n-1} - 1, b_0 = 1$$
Workings:
$b_n - 2b_{n-1} = -a_{n-1} - 1$
$a_n = 2a_{n-1} - b_{n-1} + 2$
$a_{n+1} = 2a_n - b_n + 2$
$-2a_n = -4a_{n-1} + 2b_{n-1} - 4$
$a_{n+1} + 2a_n = (2a_n - b_n + 2) + (4a_{n-1} - 2b_{n-1} + 4) $
$a_{n+1} + 2a_n = 2a_n  + 4a_{n+1} - b_n -2b_{n-1} + 6$
$a_{n+1} + 2a_n = 2a_n + 4a_{n-1} - (-a_{n-1} - 1) + 6$
$a_{n+1} + 2a_n = 2a_n + 4a_{n-1} + a_{n-1} + 7$
$a_{n+1} = 5a_{n-1} + 7 (*)$
Now I'm not sure what to next. Can I shift $(*)$ down to $a-n$.
Any help will be appreciated.
 A: One way is to define generating functions $A(z) = \sum_{n \ge 0} a_n z^n$ and $B(z) = \sum_{n \ge 0} b_n z^n$, write your recurrences with indices shifted so that there are no subtractions in indices:
$\begin{align}
a_{n + 1} &= 2 a_n - b_n + 2 \\
b_{n + 1} &= - a_n + 2 b_n - 1
\end{align}$
Multiply both recurrences by $z^n$, sum over $n \ge 0$, and recognise some sums:
$\begin{align}
\sum_{n \ge 0} a_{n + 1} z^n
  &= 2 \sum_{n \ge 0} a_n z^n 
      - \sum_{n \ge 0} b_n z^n
      + 2 \sum_{n \ge 0} z^n \\
\sum_{n \ge 0} b_{n + 1} z^n
  &= - \sum_{n \ge 0} a_n z^n
      + 2 \sum_{n \ge 0} b_n z^n
      - \sum_{n \ge 0} z^n
\end{align}$
$\begin{align}
\frac{A(z) - a_0}{z}
  &= 2 A(z) - B(z) + \frac{2}{1 - z} \\
\frac{B(z) - b_0}{z}
  &= - A(z) + 2 B(z) - \frac{1}{1 - z}
\end{align}$
The solution to this system of equations is:
$\begin{align}
A(z)
  &= \frac{z - 2 z^2}{1 - 5 z + 7 z^2 - 3 z^3} \\
  &= \frac{1}{4 (1 - 3 z)}
       - \frac{3}{4 (1 - z)}
       + \frac{1}{2 (1 - z)^2} \\
B(z)
  &= \frac{1 - 4 z + 2 z^2}{1 - 5 z + 7 z^2 - 3 z^3} \\
  &= - \frac{1}{4 (1 - 3 z)}
       + \frac{3}{4 (1 - z)}
       + \frac{1}{2 (1 - z)^2}
\end{align}$
Note that:
$$
(1 - z)^{-r}
  = \sum_{n \ge 0} (-1)^n \binom{-r}{n} z^n
  = \sum_{n \ge 0} \binom{n + r - 1}{r - 1} z^n
$$
Also, $\binom{n + r - 1}{r - 1}$ is a polynomial of degree $r - 1$ in $n$.
In particular, $\binom{n + 1}{1} = n + 1$. Picking the coefficients of $z^n$ of the above:
$\begin{align}
a_n
  &= \frac{3^n}{4}
       - \frac{3}{4}
       + \frac{n + 1}{2} \\
  &= \frac{3^n - 3}{4} + \frac{n + 1}{2} \\
b_n
  &= - \frac{3^n}{4}
       + \frac{3}{4}
       + \frac{n + 1}{2} \\
  &= - \frac{3^n - 3}{4} + \frac{n + 1}{2}
\end{align}$
A: hint: add the two equations to get: $(a_n+b_n) = (a_{n-1} + b_{n-1}) + 1\to a_n+b_n = n+1$. Can you take it from here?
