Results 1 to 4 of 4

Thread: 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 $\displaystyle H(x)=\sum_{n\ge 0}{h_nx^n}$ and $\displaystyle H(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}$
    a) Find the recurrence relation the coefficients $\displaystyle 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 $\displaystyle 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
    $\displaystyle H(x)=\frac{2}{1-2x}-\frac{1}{(1-x)^2}$

    Then my nxt step was to place it into $\displaystyle H(x)=\sum_{n\ge 0}{h_nx^n}$ form. So I get,
    $\displaystyle H(x)=2\sum_{n\ge 0}{(2x)^n-\sum_{n\ge 0}{(n+1)x^n}$ by geometric series.
    $\displaystyle =2{\sum_{n\ge 0}{(2^n-\frac{1}{2}(n+1)) x^n$
    so $\displaystyle 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. $\displaystyle h_0=\frac{1}{2}$?

    b) Find an explicit expression for $\displaystyle h_n$, $\displaystyle 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

    $\displaystyle (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

    $\displaystyle x_{n+1} = 2 x_n, x_1 = 1$

    then that's a recurrence relation. If I write

    $\displaystyle x_n = 2^n$,

    that's an explicit expression.

    It's in finding an explicit expression for $\displaystyle 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.

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

    We have the following terms:
    $\displaystyle (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,
    $\displaystyle h_n-4h_{n-1}+5h_{n-2}-2h_{n-3}=0$

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

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

    The coefficient of $\displaystyle x^2$ on RHS is $\displaystyle 2$. Hence let $\displaystyle n=2$, and equate it.
    $\displaystyle (h_2)(1)+(h_1)(-4)+(h_0)(5)=2$
    $\displaystyle h_2=2+4h_1-5h_0=2+8-5$
    i.e. $\displaystyle 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; Oct 12th 2010 at 06: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: Dec 27th 2010, 03:47 AM
  2. recurrence and generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 12th 2010, 09:49 AM
  3. Finding the generating function of a recurrence
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 29th 2009, 02:14 PM
  4. Replies: 8
    Last Post: Sep 20th 2008, 07:49 AM
  5. Recurrence Relations: Generating Functions
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: Nov 30th 2007, 12:47 PM

Search Tags


/mathhelpforum @mathhelpforum