Results 1 to 10 of 10

Math Help - Recurrence Relations: Generating Functions

  1. #1
    Newbie
    Joined
    Nov 2007
    Posts
    7

    Recurrence Relations: Generating Functions

    I was looking to figure out how to solve the following:

    The recurrence relation: a_{n}=4a_{n-1}-4a_{n-2}+4^{n}
    Given: n\ge 2 , a_{0}=2 , a_{1} = 8

    How would you go about solving this in terms of a generating function?

    Thanks!

    Kev
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    600
    Hello, Kev!

    This one requires another trick . . .


    The recurrence relation: . a_{n}\:=\:4a_{n-1}-4a_{n-2}+4^{n} .[1]
    Given: . n\ge 2,\;a_0\,=\,2,\;a_1\,=\,8

    Consider the (n+1)^{th} case: . a_{n+1} \;=\;4a_n - 4 a_{n-1} + 4^{n+1} .[2]

    . . . . . . Multiply [1] by 4: . . 4a_n \;=\;16a_{n-1} - 16a_{n-2} + 4^{n+1} .[3]


    Subtract [3] from [2]: . a_{n+1}-4a_n \;=\;4a_n - 20a_{n-1} + 16a_{n-2}

    . . . . . a_{n+1} - 8a_n + 20a_{n-1} - 16a_{n-2} \;=\;0


    Let X^k = a_k\!:\;\;X^{n+1} = 8X^n + 20X^{n-1} - 16X^{n-2} \;=\;0

    Divide by X^{n-2}\!:\;\;X^3 - 8X^2 + 20X - 16 \;=\;0

    . . which factors; . (X-2)^2(X-4) \;=\;0

    . . and has roots: . 2,\,2,\,4


    . . . . . .Go for it!

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,817
    Thanks
    316
    Awards
    1
    I must admit that I'm curious to see the generating function method myself.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    I haven't thought about recurrences and GF since college. This is an interesting topic. Here is an example of one I solved years ago. I still had the paper. I keep running into problems with the one posted. Something small I'm overlooking. Most always is. Maybe this will give you something to go by.

    Anyway, here's an example of a recurrence using GF

    a_{n}=5a_{n-1}-6a_{n-2}, \;\ a_{0}=1, \;\ a_{1}=0

    A(x)=1-6x-30x^{2}-114x^{3}-.................

    A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}

    1+\sum_{n=2}^{\infty}a_{n}x^{n}

    1+\sum_{n=2}^{\infty}(5a_{n-1}-6a_{n-2})x^{n}

    1+5\sum_{n=2}^{\infty}a_{n-1}x^{n}-6\sum_{n=2}^{\infty}a_{n-2}x^{n}

    1+5x\sum_{n=2}^{\infty}a_{n-1}x^{n-1}-6x^{2}\sum_{n=2}^{\infty}a_{n-2}x^{n-2}

    1+5x\sum_{k=1}^{\infty}a_{k}x^{k}-6x^{2}\sum_{k=0}^{\infty}a_{k}x^{k}

    1+5x\sum_{k=0}^{\infty}a_{k}x^{k}-5x(1)-6x^{2}\sum_{k=0}^{\infty}a_{k}x^{k}

    A(x)=1+5xA(x)-5x-6x^{2}A(x)

    Let y=A(x):

    y=1+5xy-5x-6x^{2}y

    y=\frac{1-5x}{6x^{2}-5x+1}=\frac{-2}{1-3x}+\frac{3}{1-2x}

    Notice the familiar geometric series solution in the PFD, \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}

    This gives us \boxed{a_{n}=3\cdot{2^{n}}-2\cdot{3^{n}}}

    Hope this helps. I can easily get the result from Maple, but that's no fun.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,659
    Thanks
    600
    Hello, Kev ... and anyone else interested,

    Thought I'd show how I crank out the recursion function.

    In the above problem, we had roots: . X \:=\:2,\,2,\,4
    . . where X the base of exponential terms.


    We now construct the function.
    It contains: 2^n and 4^n
    And because the 2 is repeated, we have the term: . n\!\cdot2^n

    The function has the form: . a(n) \;=\;A\!\cdot\!2^n + B\!\cdot\!n\!\cdot\!2^n + C\!\cdot\!4^n
    . . and we must determine A,\,B,\,C.

    We use the first two terms of the sequence: . a(0) =2,\;a(1) = 8
    . . and we can calculate the third term: . a(2) = 40


    So we have:

    \begin{array}{ccccccccc}a(0) = 2: & A\!\cdot\!2^0 + B\!\cdot\!0\!\cdot2^0 + C\!\cdot\!4^0 & = & 2 & \Rightarrow & A + C & = & 2 & [1] \\<br />
a(1) = 8: & A\!\cdot\!2^1 + B\!\cdot\!1\!\cdot\!2^1 + C\!\cdot\!4^1 & = & 8 & \Rightarrow & 2A + 2B + 4C & = & 8 & [2] \\<br />
a(2) = 40: & A\!\cdot\!2^2 + B\!\cdot\!2\!\cdot\!2^2 + C\!\cdot\!r^2 & = & 40 & \Rightarrow & 4A + 8A + 16C & = & 40 & [3]\end{array}

    Divide [3] by -4: . -A - 2B - 4C \:=\,\text{-}10
    . . . . . . Add [2]: . 2A + 2B + 4C \:=\;\;8

    And we get: . \boxed{A \:=\:\text{-}2}

    Substitute into [1]: .  \text{-}2 + C \:=\:2\quad\Rightarrow\quad \boxed{C \:=\:4}

    Substitute into [2]: . 2(\text{-}2) + 2B + 4(4) \:=\:8\quad\Rightarrow\quad \boxed{B \:=\:\text{-}2}


    The function is: . a(n) \;=\;-2\!\cdot\!2^n - 2\!\cdot\!n\!\cdot\!2^n + 4\!\cdot\!4^n  \;=\;-2^{n+1} - n\!\cdot\!2^{n+1} + 4^{n+1}

    . . = \;-(1 + n)2^{n+1} + (2^2)^{n+1} \;=\;-(n+1)2^{n+1} + 2^{2n+2} \;=\;2^{2n+2} - (n+1)2^{n+1}

    Factor: . \boxed{\:a(n) \;=\;2^{n+1}\left[2^{n+1} - (n+1)\right]\:}


    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,817
    Thanks
    316
    Awards
    1
    Quote Originally Posted by galactus View Post
    Anyway, here's an example of a recurrence using GF

    a_{n}=5a_{n-1}-6a_{n-2}, \;\ a_{0}=1, \;\ a_{1}=0

    A(x)=\sum_{n=0}^{\infty}a_{n}x^{n}
    A(x)=1+5xA(x)-5x-6x^{2}A(x)

    Let y=A(x):

    y=1+5xy-5x-6x^{2}y

    y=\frac{1-5x}{6x^{2}-5x+1}=\frac{-2}{1-3x}+\frac{3}{1-2x}

    Notice the familiar geometric series solution in the PFD, \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}

    This gives us \boxed{a_{n}=3\cdot{2^{n}}-2\cdot{3^{n}}}
    If you would be so kind...

    I'm trying to run the original question through this method and I'm running into some trouble. I know I can avoid this by using Soroban's trick of putting the recursion into a form that removes the 4^n term, but can this be done from the original problem itself?

    I'm probably being confusing. I'll just post this:
    Define a series
    A(x) = \sum_{n = 0}^{\infty}a_nx^n

    Then
    A(x) = 2 + 8x + \sum_{n = 2}^{\infty}(4a_{n - 1} - 4a_{n - 2} + 4^n)x^n

    A(x) = 2 + 8x + 4 \sum_{n = 2}^{\infty}a_{n - 1}x^n - 4 \sum_{n = 2}^{\infty} a_{n - 2}x^n + \sum_{n = 2}^{\infty}4^nx^n

    The last term is giving me problems. All I can think of to do with it is to cast it in the form
    \sum_{n = 2}^{\infty}4^nx^n = \sum_{n = 2}^{\infty}(4x)^n

    But when I complete the steps of the method to find an equation for A(x) I get
    A(x) = 2 + 8 + 4xA(x) - 8x - 4x^2A(x) - 2 - 32x + A(4x)

    Assuming I have everything else right, I'm still stuck with that A(4x) term. Any thoughts?

    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    That is the same exact snag I run into, TQ.

    I thought about leaving A(4x)=4y.

    Solving for y and using PFD, results in \frac{-7}{2x+1}-\frac{13}{2x-3}

    I don't beleive that gets us anywhere, though?.

    Alas, I am at work and don't have much time. I will try to take a glance this evening.

    Hey. This is #1000. I am now a contributor, as Janvdl reminded me.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,817
    Thanks
    316
    Awards
    1
    Quote Originally Posted by galactus View Post
    That is the same exact snag I run into, TQ.

    I thought about leaving A(4x)=4y.
    That can't work in general, I don't think. We can't assume that A(4x) = 4A(x) in general. (What's that called anyway? A homogeneous function, or something like that?)

    Quote Originally Posted by galactus View Post
    Hey. This is #1000. I am now a contributor, as Janvdl reminded me.
    Congrats!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Eater of Worlds
    galactus's Avatar
    Joined
    Jul 2006
    From
    Chaneysville, PA
    Posts
    3,001
    Thanks
    1
    With that A(4x), I was grabbing at straws. There's something to be done with that 4^n, I just don't know for sure what it is. I have never tackled any like that. If you figure it out, please let me know. I will surely reciprocate if I get lucky.
    Perhaps a search regarding generating functions and recurrence relations may prove fruitful.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member PaulRS's Avatar
    Joined
    Oct 2007
    Posts
    571
    Well: A(4x)=\sum_{n=0}^{\infty}{a_n\cdot{4^n}\cdot{x^n}}

    But we have: \sum_{n=2}^{\infty}{4^n\cdot{x^n}}

    Which are not necessarily the same

    Our equation is: A(x)\cdot{(1-2x)^2}=2+\sum_{n=2}^{\infty}{4^n\cdot{x^n}}

    We have to remember now that \frac{1}{(1-2x)^2}=\sum_{n=1}^{\infty}{n\cdot{(2x)^{n-1}}}

    Finally: A(x)=2\sum_{n=0}^{\infty}{(n+1)2^n\cdot{x^{n}}}+\l  eft(\sum_{n=0}^{\infty}{(n+1)2^n\cdot{x^{n}}}\righ  t)\cdot{\left(\sum_{n=2}^{\infty}{4^n\cdot{x^n}}\r  ight)}

    Then doing that product we are done
    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. recurrence and generating functions
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 12th 2010, 09:49 AM
  3. Generating funtion -> recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2010, 05:32 PM
  4. Replies: 0
    Last Post: October 6th 2009, 11:29 AM
  5. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 6th 2009, 07:56 PM

Search Tags


/mathhelpforum @mathhelpforum