Recurrence Relation


by pupeye11
Tags: recurrence, relation
pupeye11
pupeye11 is offline
#1
Jun15-10, 08:51 PM
P: 100
1. The problem statement, all variables and given/known data

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

[tex]
F(x)= \sum_{n \geq 2}f_nx^n
[/tex]

be the generating function for the sequence [tex]f_0,f_1,...,f_n,...[/tex]

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

[tex]
F(x)=\frac{P(x)}{Q(x)}
[/tex]

3. The attempt at a solution

[tex]
f_n+2f_{n-1}-15f_{n-2}=0
[/tex]

So since we know that [tex]F(x)=f_0+f_1x+f_2x^2+...+f_nx^n+...[/tex]

[tex]
F(x)=f_0+f_1x+f_2x^2+...+f_nx^n+...
[/tex]

[tex]
2xF(x)=2f_0x+2f_1x^2+...+2f_{n-1}x^n+...
[/tex]

[tex]
-15x^2F(x)= -15f_0x^2-...-15f_{n-2}x^n-...
[/tex]

Summing these I get

[tex]
(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
[/tex]

After some algebra and substituting [tex]f_0=1, f_1=2[/tex] I get

[tex]
F(x)=\frac{1+4x}{1+2x-15x^2}
[/tex]

So

[tex]
P(x)=1+4x
[/tex]

and

[tex]
Q(x)=1+2x-15x^2
[/tex]

Is this correct?
Phys.Org News Partner Science news on Phys.org
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes
lanedance
lanedance is offline
#2
Jun21-10, 06:59 AM
HW Helper
P: 3,309
looks reasonable to me, you can always check by diferntiating you function a few times


Register to reply

Related Discussions
Recurrence Relation Calculus & Beyond Homework 0
Recurrence Relation Help Calculus & Beyond Homework 5
Recurrence relation General Math 7
Recurrence Relation General Math 11
Recurrence Relation General Math 5