Solution 5.1.6.1.

We saw in an example above that this recurrence relation gives the sequence \(1, 3, 7, 15, 31, 63, \ldots\) which has generating function \(\dfrac{1}{1 - 3x + 2x^2}\text{.}\) We did this by calling the generating function \(A\) and then computing \(A - 3xA + 2x^2A\) which was just 1, since every other term canceled out.

But how does knowing the generating function help us? First, break up the generating function into two simpler ones. For this, we can use partial fraction decomposition. Start by factoring the denominator:

\begin{equation*} \frac{1}{1-3x + 2x^2} = \frac{1}{(1-x)(1-2x)}\text{.} \end{equation*}

Partial fraction decomposition tells us that we can write this faction as the sum of two fractions (we decompose the given fraction):

\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{a}{1-x} + \frac{b}{1-2x} \text{ ~~ for some constants } a \text{ and } b\text{.} \end{equation*}

To find \(a\) and \(b\) we add the two decomposed fractions using a common denominator. This gives

\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{a(1-2x) + b(1-x)}{(1-x)(1-2x)}\text{.} \end{equation*}

\begin{equation*} 1 = a(1-2x) + b(1-x)\text{.} \end{equation*}

This must be true for all values of \(x\text{.}\) If \(x = 1\text{,}\) then the equation becomes \(1 = -a\) so \(a = -1\text{.}\) When \(x = \frac{1}{2}\) we get \(1 = b/2\) so \(b = 2\text{.}\) This tells us that we can decompose the fraction like this:

\begin{equation*} \frac{1}{(1-x)(1-2x)} = \frac{-1}{1-x} + \frac{2}{1-2x}\text{.} \end{equation*}

This completes the partial fraction decomposition. Notice that these two fractions are generating functions we know. In fact, we should be able to expand each of them.

\begin{equation*} \frac{-1}{1-x} = -1 - x - x^2 -x^3 - x^4 - \cdots \mbox{ which generates } -1, -1, -1, -1, -1, \ldots\text{.} \end{equation*}

\begin{equation*} \frac{2}{1-2x} = 2 + 4x + 8x^2 + 16x^3 + 32x^4 + \cdots \mbox{ which generates } 2, 4, 8, 16, 32, \ldots\text{.} \end{equation*}

We can give a closed formula for the \(n\)th term of each of these sequences. The first is just \(a_n = -1\text{.}\) The second is \(a_n = 2^{n+1}\text{.}\) The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is

\begin{equation*} a_n = 2^{n+1} - 1\text{.} \end{equation*}