Solving the recurrence $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$ using generating functions 
Solve the following recurrence using generating functions: $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$.

My partial solution:
We can rewrite $a_{n+2} = 3a_{n+1} - 2a_n$, as $a_{n+2} - 3a_{n+1} + 2a_n = 0$, and we let $A(z) = \sum a_n z^n$. The goal is to compute $A(z)$ as this can be done as follows: $$A(z) - a_0 - a_1z - 3z(A(z) - a_0) + 2z^2A(z) = 0$$
$$(1-3z+2z^2)A(z) = a_0 + a_1z -3a_0z$$
$$A(z) = \frac{a_0 + (a_1 - 3a_0)z}{1-3z+2z^2}$$
$$\quad \quad = \frac{a_0 + (a_1 - 3a_0)z}{(1-z)(1-2z)}$$
$$\quad \quad = \frac{C}{(1-z)}+\frac{D}{(1-2z)}$$
And, I don't know how to continue, I cannot figure out the remaining. I'm pretty sure it is obvious, but I just cannot see it. If someone can help me I would be glad. 
 A: Some hints. 
To find $C$ and $D$, use that $a_0 = A(0)$ and $a_1 = A'(0)$. Two equations in two unknowns..
Once the above is done, use the following identity to get the formula for each $a_n$.
$${1  \over 1 - x} = 1 + x + x^2 + x^3 + ....$$
A: \begin{align}
\frac{C}{1-z}+\frac{D}{1-2z} &= \frac{C(1-2z)}{(1-z)(1-2z)} + \frac{(1-z)D}{(1-z)(1-2z)} \\\\ &= \frac{(C+D)+(-2C-D)z}{(1-z)(1-2z)} \\\\ &= \frac{(a_0)+(a_1-3a_0)z}{(1-z)(1-2z)}
\end{align}
You now have 2 linear equations and easily solve for $C$ and $D$ in terms of $a_0$ and $a_1$.
What is the power series for $\dfrac{1}{1-z}$?  It's a simple one, try long hand division, and you'll see the coefficient pattern after a few terms.  Note that $\dfrac{1}{1-2z}$ is just $\dfrac{1}{1-y}$ with $y=2z$.
Let $\displaystyle F(z) = \dfrac{1}{1-z} = \sum_{n=0}^{\infty}f_n z^n$ be that power series.
Then $\displaystyle A(z) = CF(z)+DF(2z) = \sum_{n=0}^{\infty} (C+D2^n)f_n z^n$. $\square$
A: Simple trick for partial fractions: Say yu have:
$$
\frac{a_0 + (a_1 - 3 a_0) z}{(1 - z) (1 - 2 z)} = \frac{A}{1 - z} + \frac{B}{1 - 2 z}
$$
This is supposed to be an identity, so for instance:
$\begin{align*}
\lim_{z \to 1/2} \left(
                   (1 - 2 z) 
                      \cdot \frac{a_0 + (a_1 - 3 a_0) z}{(1 - z) (1 - 2 z)}
                 \right)
  &= \lim_{z \to 1/2} \left(
                        (1 - 2 z) 
                          \cdot \frac{A}{1 - z}
                      \right)
       + \lim_{z \to 1/2} \left(
                            (1 - 2 z) 
                               \cdot \frac{B}{1 - 2 z}
                          \right) \\
\left. \frac{a_0 + (a_1 - 3 a_0) z}{(1 - z)} \right|_{z = 1/2}
   &= 0 + B \\
\frac{a_0 + (a_1 - 3 a_0) \cdot 1/2}{1/2}
   &= B
\end{align*}$
This simplifies to $B = a_1 - a_0$.
The same works for $A$.
