Finding sequence that's defined by a recurrence relation

Question

This is the problem that I ran into when doing practice in my textbook.

How do I find the sequence (call it $a_n$) that's defined by recurrence relation whose generating function is $\frac 4 {-x^2-2x+3}$?

Help appreciated!

Answer 1

We use partial fractions. So we want to find integers $A$ and $B$ such that $$\frac{4}{-x^2 -2x+3}=\frac{A}{3+x}+\frac{B}{1-x}.$$ There are general procedures, but we can see that $A=1$, $B=1$ work. Now $$\frac{1}{1-x}=1+x+x^2+x^3+\cdots=\sum_0^\infty x^n.$$

Expanding $\frac{1}{3-x}$ takes more work. Rewrite as $$\frac{1}{3}\frac{1}{1-\left(-\frac{x}{3}\right)}.$$ When we expand we get $$\frac{1}{3}\sum_0^\infty (-1)^n\frac{1}{3^n}x^n.$$

Put the pieces together to get the coefficient of $x^n$.

Answer 2

The main part is partial fractions, which you have to write in a funny way

$$ \frac{4}{-x^2-2x+3}=\frac{1}{3+x} + \frac{1}{1-x}=$$ $$ =\frac{1}{3}\frac{1}{1+\frac{x}{3}}+\frac{1}{1-x}$$

Now use the known formula for geometric series: $$\sum_{n\ge 0} r^n=\frac{1}{1-r}$$

to get $$\frac{4}{-x^2-2x+3}=\frac{1}{3}\sum_{n\ge0} (-1/3)^nx^n + \sum_{n\ge 0} x^n=$$ $$=\sum_{n\ge 0} \left(1-(-1/3)^{n+1}\right)x^n$$