Results 1 to 7 of 7

Math Help - Closed-form solution of a recurrence relation.

  1. #1
    Junior Member
    Joined
    Jan 2010
    Posts
    52
    Thanks
    17

    Closed-form solution of a recurrence relation.

    Suppose you have a recurrence relation like:
    {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm (1)
    With {x_0} = {x_1} = 1

    And you want to find the closed form, of it ( i.e {x_n}=f(n) ).
    In the Mathematics for the analysis of Algorithms, by Knuth and Greene it has the following procedure:

    We construct a function G(z): G(z) = \sum\limits_i {{x_i}{z^i}}

    Then we multiply (1) by {z^{n+2}} and sum over all n obtaining:
    \sum\limits_{n \ge 0} {{x_{n + 2}}{z^{n + 2}}}  - 3z\sum\limits_{n \ge 0} {{x_{n + 1}}{z^{n + 1}}}  + 2{z^2}\sum\limits_{n \ge 0} {{x_n}{z^n}}  = \sum\limits_{n \ge 0} {n{z^{n + 2}}}  \Rightarrow
    (G(z) - z - 1) - 3z(G(z) - 1) + 2{z^2}G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}}} \Rightarrow
      G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}(1 - 3z + 2{z^2})}} + \frac{{ - 2z + 1}}{{1 - 3z + 2{z^2}}}

    And now it says that we would like to recover the coefficient of {z^n} in G(z).
    a) But what does that mean? The only z powers i see in the last equation is {z}, {z^2}, {z^3}. So what coefficient of {z^n} is he talking about?

    And then it says that if the denominators of the fractions in G(z) where linear the recovery problem would be simple and that each term would just be a geometric series?
    b) How come the last one? What exactly does it mean?


    And now the most important question, which is about the derivation of the solution.
    Book continues saying that since the denominators of the fractions in G(z) are not linear, we express the solution for G(z) in partial fractions so we obtain:
    G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} - \frac{1}{{{{(1 - z)}^3}}} (2)

    And now it says that we should note that the only nonlinear denominators are just higher powers of a linear factor.
    So these terms can be expanded by the binomial theorem and then {x_n} can be easily computed to be:
    {x_n} = {2^n} - \frac{{{n^2} + n}}{2}

    c) So my question is: How {x_n} can be easily computed from (2)???? I don't get it.

    Any help with a), b), c) questions and especially with c)?


    Thanks in advance.
    Last edited by ChessTal; July 4th 2011 at 06:52 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    678
    Thanks
    32

    Re: Closed-form solution of a recurrence relation.

    We expand G(z) in power series: \frac 1{1-2z} = \sum_{n=0}^{+\infty}2^nz^n; \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^{n-1}; \frac 1{(1-z)^3} =\frac 12\sum_{n=2}^{+\infty}n(n-1)z^{n-2}.
    Last edited by girdav; July 4th 2011 at 04:58 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Jan 2010
    Posts
    52
    Thanks
    17

    Re: Closed-form solution of a recurrence relation.

    Quote Originally Posted by girdav View Post
    We expand G(z) in power series: \frac 1{1-2z} = \sum_{n=0}^{+\infty}2^nz^n
    \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^n
    \frac 1{(1-z)^3} =\frac 12\sum_{n=2}^{+\infty}n(n-1)z^{n-2}.
    Is the second one a typo?
    I mean the correct one should have been:
    \frac 1{(1-z)^2} = \sum_{n=1}^{+\infty}nz^{n-1}
    Right?

    But even that way, i don't seem to derive the expected solution of:
    {x_n} = {2^n} - \frac{{{n^2} + n}}{2}


    Here is why:
    G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} + \frac{1}{{{{(1 - z)}^3}}}\Rightarrow
    G(z) = \sum\limits_{n = 0}^{ + \infty } {{2^n}{z^n}}  + \sum\limits_{n = 1}^{ + \infty } {n{z^{n - 1}}}  + \frac{1}{2}\sum\limits_{n = 2}^{ + \infty } {n(n - 1){z^{n - 2}}}  \Rightarrow
    G(z) = \sum\limits_{n = 0}^{ + \infty } {{2^n}{z^n}}  + \sum\limits_{n = 0}^{ + \infty } {(n + 1){z^n}}  + \frac{1}{2}\sum\limits_{n = 0}^{ + \infty } {(n + 2)(n + 1){z^n}}  \Rightarrow
    G(z) = \sum\limits_{n = 0}^{ + \infty } {\left( {{z^n}({2^n} + (n + 1) + (n + 2)(n + 1))} \right)}  \Rightarrow
    G(z) = \sum\limits_{n = 0}^{ + \infty } {\left( {{z^n}({2^n} + (n + 2)(n + 3))} \right)}

    So what is exactly the whole deal i'm missing? What i'm getting wrong?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    678
    Thanks
    32

    Re: Closed-form solution of a recurrence relation.

    Yes, the second one was a typo and I have corrected it.
    There is a problem in (2): we have G(0) =1 whereas with (2) we get G(0) =3. I guess there should be a "-", but I didn't look where. You missed the \frac 12 between the lines 3 and 4 when you write G(z) with power series.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Jan 2010
    Posts
    52
    Thanks
    17

    Re: Closed-form solution of a recurrence relation.

    Quote Originally Posted by girdav View Post
    Yes, the second one was a typo and I have corrected it.
    There is a problem in (2): we have G(0) =1 whereas with (2) we get G(0) =3. I guess there should be a "-", but I didn't look where. You missed the \frac 12 between the lines 3 and 4 when you write G(z) with power series.
    Yes the calculated G(z) in (2) i gave in the initial post** was wrong, there is a minus sign in the last term instead of a positive one i previously had .
    So everything makes sense now, thanks.

    **I corrected the initial post now.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor FernandoRevilla's Avatar
    Joined
    Nov 2010
    From
    Madrid, Spain
    Posts
    2,162
    Thanks
    45

    Re: Closed-form solution of a recurrence relation.

    Quote Originally Posted by ChessTal View Post
    Suppose you have a recurrence relation like: {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm (1) With {x_0} = {x_1} = 1
    If you want to practice, here you have a similar problem I solved to the students of Industrial Engineering .
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Closed-form solution of a recurrence relation.

    Quote Originally Posted by ChessTal View Post
    Suppose you have a recurrence relation like:
    {x_{n + 2}} - 3{x_{n + 1}} + 2{x_n} = n{\rm (1)
    With {x_0} = {x_1} = 1

    And you want to find the closed form, of it ( i.e {x_n}=f(n) ).
    In the Mathematics for the analysis of Algorithms, by Knuth and Greene it has the following procedure:

    We construct a function G(z): G(z) = \sum\limits_i {{x_i}{z^i}}

    Then we multiply (1) by {z^{n+2}} and sum over all n obtaining:
    \sum\limits_{n \ge 0} {{x_{n + 2}}{z^{n + 2}}}  - 3z\sum\limits_{n \ge 0} {{x_{n + 1}}{z^{n + 1}}}  + 2{z^2}\sum\limits_{n \ge 0} {{x_n}{z^n}}  = \sum\limits_{n \ge 0} {n{z^{n + 2}}}  \Rightarrow
    (G(z) - z - 1) - 3z(G(z) - 1) + 2{z^2}G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}}} \Rightarrow
      G(z) = \frac{{{z^3}}}{{{{(1 - z)}^2}(1 - 3z + 2{z^2})}} + \frac{{ - 2z + 1}}{{1 - 3z + 2{z^2}}}

    And now it says that we would like to recover the coefficient of {z^n} in G(z).
    a) But what does that mean? The only z powers i see in the last equation is {z}, {z^2}, {z^3}. So what coefficient of {z^n} is he talking about?

    And then it says that if the denominators of the fractions in G(z) where linear the recovery problem would be simple and that each term would just be a geometric series?
    b) How come the last one? What exactly does it mean?


    And now the most important question, which is about the derivation of the solution.
    Book continues saying that since the denominators of the fractions in G(z) are not linear, we express the solution for G(z) in partial fractions so we obtain:
    G(z) = \frac{1}{{1 - 2z}} + \frac{1}{{{{(1 - z)}^2}}} - \frac{1}{{{{(1 - z)}^3}}} (2)

    And now it says that we should note that the only nonlinear denominators are just higher powers of a linear factor.
    So these terms can be expanded by the binomial theorem and then {x_n} can be easily computed to be:
    {x_n} = {2^n} - \frac{{{n^2} + n}}{2}

    c) So my question is: How {x_n} can be easily computed from (2)???? I don't get it.

    Any help with a), b), c) questions and especially with c)?


    Thanks in advance.
    The way to get (2) from (*)

    (*) \frac{z^3}{(1-z)^3(1-2z)}=\frac{z^2}{(1-z)^2}\cdot\frac{z}{(1-z)(1-2z)}=\big{(}\frac{z}{1-z}\big{)}^2\cdot\frac{z}{(1-z)(1-2z)}


    Now, \frac{z}{1-z}=\frac{1-z-1}{1-z}=1-\frac{1}{1-z}

    and:

    \frac{z}{(1-z)(1-2z)}=\frac{1}{1-2z}-\frac{1}{1-z})

    Hence (*) becomes to:


    \big{(}1-\frac{1}{1-z}\big{)}^2\cdot\big{(}\frac{1}{1-2z}-\frac{1}{1-z}\big{)}=\big{(}1-\frac{2}{1-z}+\frac{1}{(1-z)^2}\big{)}\big{(}\frac{1}{1-2z}-\frac{1}{1-z}\big{)}=\frac{1}{1-2z}-\frac{1}{1-z}-\frac{2}{(1-z)(1-2z)}+\frac{2}{(1-z)^2}+\frac{1}{(1-z)^2(1-2z)}-\frac{1}{(1-z)^3}


    But:


    -\frac{2}{(1-z)(1-2z)}+\frac{1}{(1-z)^2(1-2z)}=\frac{1}{1-2z}\big{(}\frac{1}{(1-z)^2}-\frac{2}{1-z}\big{)}=\frac{1}{1-2z}\frac{2z-1}{(1-z)^2}=-\frac{1}{(1-z)^2}


    So:

    \frac{1}{1-2z}-\frac{1}{1-z}-\frac{2}{(1-z)(1-2z)}+\frac{2}{(1-z)^2}+\frac{1}{(1-z)^2(1-2z)}-\frac{1}{(1-z)^3}=\frac{1}{1-2z}-\frac{1}{1-z}+\frac{2}{(1-z)^2}-\frac{1}{(1-z)^3}-\frac{1}{(1-z)^2}=\frac{1}{1-2z}-\frac{1}{1-z}-\frac{1}{(1-z)^3}+\frac{1}{(1-z)^2}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Closed form for recurrence function
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 30th 2011, 01:59 PM
  2. general solution of a recurrence relation
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2010, 10:55 PM
  3. Replies: 4
    Last Post: May 3rd 2009, 10:31 PM
  4. Find solution to a recurrence relation...
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 20th 2009, 12:17 PM
  5. Linear recurrence sequence, closed form.
    Posted in the Algebra Forum
    Replies: 6
    Last Post: February 21st 2009, 08:20 AM

Search Tags


/mathhelpforum @mathhelpforum