Results 1 to 3 of 3

Math Help - Generating functions - a reccurence to solve

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    1

    Generating functions - a reccurence to solve

    I'm not sure how to solve the following reccurence:
    By using generating functions solve the reccurence. Find both the generating function and the closed form solution of the sequence:

    \\a_{0} =0, \\a_{1} = 1, \\a_{n} = 7a_{n-1} - 10a_{n-2} + 2 , \:  for \:  n \geq 2
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1
    Quote Originally Posted by Muvena View Post
    I'm not sure how to solve the following reccurence:
    By using generating functions solve the reccurence. Find both the generating function and the closed form solution of the sequence:

    \\a_{0} =0, \\a_{1} = 1, \\a_{n} = 7a_{n-1} - 10a_{n-2} + 2 , \:  for \:  n \geq 2

    Let f(x)=a_0+a_1x+a_2x^2+... be the generating function of a_n.

    Let us write:

    f(x)=\sum_{i = 0}^\infty a_ix^i=0+x+\sum_{i = 2}^\infty a_ix^i=x+\sum_{i = 2}^\infty(7a_{i-1} - 10a_{i-2} + 2 )x^i=x+\sum_{i = 2}^\infty7a_{i-1}x^i-\sum_{i = 2}^\infty10a_{i-2}x^i+\sum_{i = 2}^\infty2x^i=x+x\sum_{j = 1}^\infty7a_{j}x^j-x^2\sum_{j = 0}^\infty10a_{j}x^j+\frac{2x^2}{1-x}=x+7x(f(x))-10x^2(f(x))+\frac{2x^2}{1-x}

    So:

     f(x)=x+7x(f(x))-10x^2(f(x))+\frac{2x^2}{1-x}

     f(x)\{1-7x-+10x^2 \}=x+\frac{2x^2}{1-x}

      f(x)=\frac{x+\frac{2x^2}{1-x}}{1-7x-+10x^2}

    Now, to find closed form solution of the sequence you need to find the coefficient of x^k in Taylor's series of f(x). This task I'll leave it to you.
    Last edited by Also sprach Zarathustra; May 27th 2011 at 05:54 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2011
    Posts
    12
    Thanks a lot for your help!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 27th 2010, 03:47 AM
  2. Solve a reccurence relation
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2009, 11:59 PM
  3. generating functions
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 24th 2009, 07:01 AM
  4. Generating Functions
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: April 25th 2008, 04:43 PM
  5. Generating functions...need some help here
    Posted in the Calculus Forum
    Replies: 4
    Last Post: January 31st 2008, 04:32 PM

Search Tags


/mathhelpforum @mathhelpforum