Results 1 to 4 of 4

Math Help - Generating funtion -> recurrence relation

  1. #1
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100

    Generating funtion -> recurrence relation

    Hi. I have this problem.

    Let H(x)=\sum_{n\ge 0}{h_nx^n} and H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}
    a) Find the recurrence relation the coefficients h_n satisfy. Be sure to state the initial values.

    Okay, this is what I did so far. I went about finding the partial fractions for this H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}. And assuming I did it correctly (I checked it on a calculator so it should be correct)... I ended up with this
    H(x)=\frac{2}{1-2x}-\frac{1}{(1-x)^2}

    Then my nxt step was to place it into H(x)=\sum_{n\ge 0}{h_nx^n} form. So I get,
    H(x)=2\sum_{n\ge 0}{(2x)^n-\sum_{n\ge 0}{(n+1)x^n} by geometric series.
    =2{\sum_{n\ge 0}{(2^n-\frac{1}{2}(n+1)) x^n
    so h_n=2(2^n-\frac{1}{2}(n+1))

    It doesn't look right to me. Because I don't know what the initial values are. h_0=\frac{1}{2}?

    b) Find an explicit expression for h_n, n\ge0

    How do I do this one? What would be the difference between finding the recurrence relation??

    Thanks for your help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Hi lpd,

    On finding a recurrence relation, probably you want to start with

    (1-x)^2 (1-2x) H(x) = 1 - 2x + 2x^2.

    See what happens when you multiply everything out-- it should give you information about the coefficients of H(x).

    A recurrence relation is not the same thing as finding an explicit expression for the coefficients. For example, if I write

    x_{n+1} = 2 x_n, x_1 = 1

    then that's a recurrence relation. If I write

    x_n = 2^n,

    that's an explicit expression.

    It's in finding an explicit expression for h_n that you may find partial fractions useful.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    lpd
    lpd is offline
    Member
    Joined
    Sep 2009
    Posts
    100
    cool. okay. this is what i did now.

    ((1-x)^2(1-2x))H(x)=1-2x+2x^2
    (1-4x+5x^2-2x^3)H(x)= 1-2x+2x^2
    coefficient of x^n for n \ge 3 is 0 from RHS

    We have the following terms:
    (h_n x^n)1, (h_{n-1} x^{n-1})(-4x),(h_{n-2} x^{n-2})(5x^2),(h_{n-3} x^{n-3})(-2x^3).
    These terms must add up to zero,
    h_n-4h_{n-1}+5h_{n-2}-2h_{n-3}=0

    The constant term on RHS is 1. Hence the constant term of h(x) is 1. i.e h_0=1

    The coefficient of x on RHS is -2. Hence let n=1, and equate it.
    (h_1)(1)+(h_0)(-4)=-2, h_1=-2+4h_0
    i.e h_1=2

    The coefficient of x^2 on RHS is 2. Hence let n=2, and equate it.
    (h_2)(1)+(h_1)(-4)+(h_0)(5)=2
    h_2=2+4h_1-5h_0=2+8-5
    i.e. h_2=5

    Was I on the right track?

    and for b) to find the explicit expression of h(x), I have somewhat done it already. i.e. finding the partial fraction. so is correct right?
    Last edited by lpd; October 12th 2010 at 07:28 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    You have the right idea, but you need to double-check your algebra.

    To see if your explicit solution is correct, substitute it into your recurrence relation. It should reduce to an identity.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 27th 2010, 04:47 AM
  2. recurrence and generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2010, 10:49 AM
  3. Finding the generating function of a recurrence
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 29th 2009, 03:14 PM
  4. Replies: 8
    Last Post: September 20th 2008, 08:49 AM
  5. Recurrence Relations: Generating Functions
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 30th 2007, 01:47 PM

Search Tags


/mathhelpforum @mathhelpforum