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?

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