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.
in-context