Results 1 to 2 of 2

Thread: recurrence and generating functions

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

    recurrence and generating functions

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

    Then,

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

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

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

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

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

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

    So,

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

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

    Solving for $\displaystyle A,B$ in

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

    we obtain

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

    and

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

    Thus,

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

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

    According to my exam, the correct answer is $\displaystyle 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 $\displaystyle a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $\displaystyle 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 $\displaystyle a_{n}=2a_{n-1}+3^{n}$ with $\displaystyle a_{0}=6$.

    Then,

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

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

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

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

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

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

    So,

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

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

    Solving for $\displaystyle A,B$ in

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

    we obtain

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

    and

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

    Thus,

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

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

    According to my exam, the correct answer is $\displaystyle 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 $\displaystyle a_{1}$. Do I just start the infinite series at one and move on like any other problem (i.e., $\displaystyle G(x)=\sum_{1}^{\infty}a_{n}x^{n}$)? Finally, under what conditions does this method for solving recurrence relations fail?
    $\displaystyle \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: Dec 27th 2010, 03:47 AM
  2. Generating funtion -> recurrence relation
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 12th 2010, 05:32 PM
  3. Replies: 0
    Last Post: Oct 6th 2009, 11:29 AM
  4. Finding the generating function of a recurrence
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Aug 29th 2009, 02:14 PM
  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