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.
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}$