Results 1 to 10 of 10

Thread: 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: $\displaystyle a_{n}=4a_{n-1}-4a_{n-2}+4^{n}$
    Given: $\displaystyle 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
    12,028
    Thanks
    848
    Hello, Kev!

    This one requires another trick . . .


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

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

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


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

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


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

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

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

    . . and has roots: .$\displaystyle 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
    11,152
    Thanks
    731
    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,002
    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

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

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

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

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

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

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

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

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

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

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

    Let y=A(x):

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

    $\displaystyle 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, $\displaystyle \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

    This gives us $\displaystyle \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
    12,028
    Thanks
    848
    Hello, Kev ... and anyone else interested,

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

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


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

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

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


    So we have:

    $\displaystyle \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] \\
    a(1) = 8: & A\!\cdot\!2^1 + B\!\cdot\!1\!\cdot\!2^1 + C\!\cdot\!4^1 & = & 8 & \Rightarrow & 2A + 2B + 4C & = & 8 & [2] \\
    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: .$\displaystyle -A - 2B - 4C \:=\,\text{-}10$
    . . . . . . Add [2]: .$\displaystyle 2A + 2B + 4C \:=\;\;8$

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

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

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


    The function is: .$\displaystyle 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}$

    . . $\displaystyle = \;-(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: .$\displaystyle \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
    11,152
    Thanks
    731
    Awards
    1
    Quote Originally Posted by galactus View Post
    Anyway, here's an example of a recurrence using GF

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

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

    Let y=A(x):

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

    $\displaystyle 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, $\displaystyle \sum_{n=1}^{\infty}a_{n}=\frac{1}{1-x}$

    This gives us $\displaystyle \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 $\displaystyle 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
    $\displaystyle A(x) = \sum_{n = 0}^{\infty}a_nx^n$

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

    $\displaystyle 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
    $\displaystyle \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
    $\displaystyle 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,002
    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 $\displaystyle \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
    11,152
    Thanks
    731
    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 $\displaystyle 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,002
    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: $\displaystyle A(4x)=\sum_{n=0}^{\infty}{a_n\cdot{4^n}\cdot{x^n}}$

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

    Which are not necessarily the same

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

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

    Finally:$\displaystyle 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: 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. Generating funtion -> recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 12th 2010, 05:32 PM
  4. Replies: 0
    Last Post: Oct 6th 2009, 11:29 AM
  5. recurrence relations - degree of the recurrence
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 6th 2009, 07:56 PM

Search Tags


/mathhelpforum @mathhelpforum