Showing that generating function coefficients agree with recurrence relation I have the recurrence relation $a_n = 3a_{n-1} + 4a_{n-2}$ with $a_0 = 1, a_1 = 0$. The solution to this is $a_n = \frac{4^n}{5} + \frac{4(-1)^n}{5}$. The generating function is $g(x) = \frac{1-3x}{1-3x-4x^2} = (1-3x)(\sum_{i=0}^{\infty}(-1)^ix^i)(\sum_{k=0}^{\infty}4^kx^k$). I need to show that, for any non-negative integer $n$, the coefficient of $x^n$ is equal to $a_n$ (the solution to the recurrence relation). But how can I find a general formula for this $N$th coefficient, given that there are so many possibilities for what $i$ and $k$ could be?
 A: One way is expanding $\sum_{n=0}^\infty a_nx^n$. Note that $a_n=\frac{4^n}{5} + \frac{4(-1)^n}{5}$ evaluated at $n=0$ and $n=1$ coincides with the stated $a_0=1, a_1=0$, so that we can focus at
\begin{align*}
a_n=\frac{4^n}{5} + \frac{4(-1)^n}{5}\qquad\qquad n\geq 0
\end{align*}

Recalling the geometric series formula we obtain
\begin{align*}
\color{blue}{\sum_{n=0}^\infty a_n x^n}&=\sum_{n=0}^\infty\left(\frac{1}{5}4^n+\frac{4}{5}(-1)^n\right)x^n\\
&=\frac{1}{5}\sum_{n=0}^\infty 4^nx^n+\frac{4}{5}\sum_{n=0}^\infty(-1)^nx^n\\
&=\frac{1}{5}\sum_{n=0}^\infty(4x)^n+\frac{4}{5}\sum_{n=0}^\infty(-x)^n\\
&=\frac{1}{5}\cdot\frac{1}{1-4x}+\frac{4}{5}\cdot\frac{1}{1+x}\\
&=\frac{1}{5}\cdot\frac{1+x+4(1-4x)}{(1-4x)(1+x)}\\
&\,\,\color{blue}{=\frac{1-3x}{1-3x-4x^2}}
\end{align*}

A: Take your generating function, write it as partial fractions:
$\begin{equation*}
g(z)
  = \frac{4}{5 (1 + z)} + \frac{1}{5 (1 - 4 z)}
\end{equation*}$
Thus (two geometric series) you have directly:
$\begin{equation*}
 [z^n] g(z)
   = \frac{4}{5} \cdot (-1)^n + \frac{1}{5} \cdot 4^n
\end{equation*}$
