We saw in an example above that this recurrence relation gives the sequence which has generating function We did this by calling the generating function and then computing 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:
Partial fraction decomposition tells us that we can write this faction as the sum of two fractions (we decompose the given fraction):
To find and we add the two decomposed fractions using a common denominator. This gives
so
This must be true for all values of If then the equation becomes so When we get so This tells us that we can decompose the fraction like this:
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.
We can give a closed formula for the th term of each of these sequences. The first is just The second is The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is