Recurrence Relation

  1. 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?
     
  2. jcsd
  3. lanedance

    lanedance 3,307
    Homework Helper

    looks reasonable to me, you can always check by diferntiating you function a few times
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook