# Recurrence Relation

1. ### pupeye11

100
1. The problem statement, all variables and given/known data

The sequence $$f_n$$ is defined by $$f_0=1, f_1=2$$ and $$f_n=-2f_{n-1}+15f_{n-2}$$ when $$n \geq 2$$. Let

$$F(x)= \sum_{n \geq 2}f_nx^n$$

be the generating function for the sequence $$f_0,f_1,...,f_n,...$$

Find polynomials P(x) and Q(x) such that

$$F(x)=\frac{P(x)}{Q(x)}$$

3. The attempt at a solution

$$f_n+2f_{n-1}-15f_{n-2}=0$$

So since we know that $$F(x)=f_0+f_1x+f_2x^2+...+f_nx^n+...$$

$$F(x)=f_0+f_1x+f_2x^2+...+f_nx^n+...$$

$$2xF(x)=2f_0x+2f_1x^2+...+2f_{n-1}x^n+...$$

$$-15x^2F(x)= -15f_0x^2-...-15f_{n-2}x^n-...$$

Summing these I get

$$(1+2x-15x^2)F(x)=f_0+(f_1+2f_0)x+(f_2+2f_1-15f_0)x^2+...+(f_n+2f_{n-1}-15f_{n-2})x^n$$

After some algebra and substituting $$f_0=1, f_1=2$$ I get

$$F(x)=\frac{1+4x}{1+2x-15x^2}$$

So

$$P(x)=1+4x$$

and

$$Q(x)=1+2x-15x^2$$

Is this correct?

2. ### lanedance

3,307
looks reasonable to me, you can always check by diferntiating you function a few times