Determining Sequence From Generating Functions

125 Views Asked by At

Consider these two functions $$F(x) = \sum_{n=0}^{\infty} a_nx^n = \frac{1-5x}{1-4x+3x^2}$$

and $$G(x) = \sum_{n=0}^{\infty} a_nx^n = \frac{3+3x}{1+x-2x^2}$$

I can see from this post that the general strategy is to expand the polynomial, but the second method given, for a fraction, is a trick that doesn't work in this case.

How can I solve these two problems?

1

There are 1 best solutions below

0
On BEST ANSWER

Let's look at one and the other works the same way. Since we can factorize the denominator we can write it as partial fractions.

$$F(x)=\frac{1-5x}{3x^2-4x+1}=\frac{2}{1-x}-\frac1{1-3x}=\left(2\sum_{i=0}^{\infty}x^i\right)-\left(\sum_{i=0}^{\infty}(3x)^i\right) \\ \implies F(x)=\sum_{i=0}^{\infty}(2-3^i)x^i$$

Note: Sum of geometric series $1+x+x^2+\cdots = \frac{1}{1-x}$