Showing that generating function coefficients agree with recurrence relation

Question

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?

Answer 1

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

Answer 2

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