Results 1 to 2 of 2

Math Help - recurrence and generating functions

  1. #1
    Senior Member Danneedshelp's Avatar
    Joined
    Apr 2009
    Posts
    303

    recurrence and generating functions

    Suppose a_{n}=2a_{n-1}+3^{n} with a_{0}=6.

    Then,

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

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

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

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

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

    =6+2xG(x)+\frac{1}{1-3x}.

    So,

    G(x)-2xG(x)=6+\frac{1}{1-3x}

    G(x)=\frac{7-18x}{(1-3x)(1-2x)}

    Solving for A,B in

    G(x)=\frac{7-18x}{(1-3x)(1-2x)}=\frac{A}{1-3x}+\frac{B}{1-2x}

    we obtain

    A=\lim_{x\rightarrow\frac{1}{3}}=(1-3x)G(x)=3

    and

    B=\lim_{x\rightarrow\frac{1}{2}}=(1-2x)G(x)=4

    Thus,

    G(x)=\frac{3}{1-3x}+\frac{4}{1-2x}=3\sum_{0}^{\infty}3^{n}x^{n}+4\sum_{0}^{\infty  }2^{n}x^{n}.

    So, the general formula for the recurrence is given by

    a_{n}=(3)3^{n}+(4)2^{n}.

    According to my exam, the correct answer is a_{n}=(3)3^{n}+(3)2^{n}, which I get when I use the method of undetermined coefficients. However, I am not seeing my mistake when I use the method above.

    Also, lets say I have a recurrence relation starting with intitial contition a_{1}. Do I just start the infinite series at one and move on like any other problem (i.e., G(x)=\sum_{1}^{\infty}a_{n}x^{n})? Finally, under what conditions does this method for solving recurrence relations fail?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by Danneedshelp View Post
    Suppose a_{n}=2a_{n-1}+3^{n} with a_{0}=6.

    Then,

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

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

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

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

    =6+2x\sum_{1}^{\infty}a_{n-1}x^{n-1}+\frac{1}{1-3x} See below

    =6+2xG(x)+\frac{1}{1-3x}.

    So,

    G(x)-2xG(x)=6+\frac{1}{1-3x}

    G(x)=\frac{7-18x}{(1-3x)(1-2x)}

    Solving for A,B in

    G(x)=\frac{7-18x}{(1-3x)(1-2x)}=\frac{A}{1-3x}+\frac{B}{1-2x}

    we obtain

    A=\lim_{x\rightarrow\frac{1}{3}}=(1-3x)G(x)=3

    and

    B=\lim_{x\rightarrow\frac{1}{2}}=(1-2x)G(x)=4

    Thus,

    G(x)=\frac{3}{1-3x}+\frac{4}{1-2x}=3\sum_{0}^{\infty}3^{n}x^{n}+4\sum_{0}^{\infty  }2^{n}x^{n}.

    So, the general formula for the recurrence is given by

    a_{n}=(3)3^{n}+(4)2^{n}.

    According to my exam, the correct answer is a_{n}=(3)3^{n}+(3)2^{n}, which I get when I use the method of undetermined coefficients. However, I am not seeing my mistake when I use the method above.

    Also, lets say I have a recurrence relation starting with intitial contition a_{1}. Do I just start the infinite series at one and move on like any other problem (i.e., G(x)=\sum_{1}^{\infty}a_{n}x^{n})? Finally, under what conditions does this method for solving recurrence relations fail?
    \sum_{1}^{\infty}3^{n}x^{n} = \frac{1}{1-3x}-1
    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. Generating funtion -> recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 12th 2010, 05:32 PM
  3. Replies: 0
    Last Post: October 6th 2009, 11:29 AM
  4. Finding the generating function of a recurrence
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 29th 2009, 02:14 PM
  5. Recurrence Relations: Generating Functions
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: November 30th 2007, 12:47 PM

Search Tags


/mathhelpforum @mathhelpforum