# Recurrence Relation

by pupeye11
Tags: recurrence, relation
 P: 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?