<s>[INST] 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. 
 [/INST] 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$.
</s>