Results 1 to 5 of 5

Math Help - Ordinary generating function

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Ordinary generating function

    c_{0}=1 and c_{n}=3c_{n-1}+3^{n} for n\geq1

    c_{n}x^{n}=3c_{n-1}x^{n}+3^{n}x^{n}

    \sum_{n\geq1}c_{n}x^{n}= \sum_{n\geq1}3c_{n-1}x^{n}+\sum_{n\geq1}3^{n}x^{n}

    LHS \sum_{n\geq1}c_{n}x^{n}= \left(\sum_{n\geq0}c_{n}x^{n}\right)-1=h(x)-1

    RHS 1st term \sum_{n\geq1}3c_{n-1}x^{n}= 3x\sum_{n\geq1}c_{n-1}x^{n-1}=3xh(x)

    2nd term \sum_{n\geq1}3^{n}x^{n}= \left(\sum_{n\geq0}3^{n}x^{n}\right)-1<br />
    So h(x)-1=3xh(x)+\frac{1}{1-3x}-1; \left(1-3x\right)h(x)=\frac{1}{1-3x} And h(x)=\frac{1}{\left(1-3x\right)^{2}}

    I don't know how to turn this into the answer in the book which is c_{n}=(n+1)3^{n}

    If I've made an error, could someone please point it out?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,740
    Thanks
    645
    Hello, oldguynewstudent!

    c_0=1\:\text{ and }\:c_n \:=\:3c_{n-1}+3^n\:\text{ for }n\geq1

    I cranked out the first few terms and looked for a pattern.


    . . \begin{array}{cccccccccc}<br />
c_0 &=& 1 &=& 1\cdot1 &=& 1\cdot3^0 \\<br />
c_1 &=& 6 &=& 2\cdot3 &=& 2\cdot3^1 \\<br />
c_2 &=& 27 &=& 3\cdot9 &=& 3\cdot3^2 \\<br />
c_3 &=& 108 &=& 4\cdot27 &=& 4\cdot3^4 \\<br />
c_4 &=& 405 &=& 5\cdot81 &=& 5\cdot3^4 \\<br />
c_5 &=& 1458 &=& 6\cdot243 &=& 6\cdot3^5 \\<br />
\vdots && \vdots && \vdots && \vdots \end{array}


    Therefore: . c_n \;=\;(n+1)\cdot 3^n

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Your answer looks fine. The last thing you have to do is find the Taylor series for h(x)=\frac{1}{(1-3x)^2}.

    You can start with the geometric series \frac{1}{1-x}=1+x+x^2+x^3\ldots+x^n+\ldots

    Then, \frac{1}{1-3x}=1+3x+9x^2+27x^3+\ldots + 3^nx^n+\ldots

    Now, differentiating both sides, \frac{3}{(1-3x)^2}=3+18x+81x^2+324x^3+\ldots+n3^nx^{n-1}+\ldots

    Finally, dividing both sides by 3, \frac{1}{(1-3x)^2}=1+6x+27x^2+108x^3+\ldots +n3^{n-1}x^{n-1}+\ldots

    We see that c_n=n 3^{n-1} for n=2, 3, 4, \ldots (You can shift the index by one to get book's solution.)
    Last edited by roninpro; July 25th 2010 at 01:03 AM. Reason: Fixed index for sequence
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member Renji Rodrigo's Avatar
    Joined
    Sep 2009
    From
    Rio de janeiro
    Posts
    38
    a general solution for recurrences in the form

     f(n+1)=a_n f(n)+b_n
    can be found using this trick

    write

     f(n)=h(n) \prod\limits^{n-1}_{k=1} a_k

    then use it on the equation

     h(n+1) \prod\limits^{n}_{k=1} a_k = h(n)\prod\limits^{n}_{k=1} a_k  +b_n

    so

     \Delta h(k) =\frac{b_n } {\prod\limits^{n}_{k=1} a_k}
    is a telescoping summation, finding h(n) we find f(n)

    by example, puting a_k=3, we have h(0)=3 , by the initial condition so
    h(n)=3(n+1) so f(n)=3^n(n+1).
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Yes, I see your point, but in the context of ordinary generating functions, I believe this approach would not go over with my professor.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Finding probability function of moment generating function
    Posted in the Advanced Statistics Forum
    Replies: 6
    Last Post: July 4th 2011, 04:03 PM
  2. Generating function
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: May 20th 2010, 05:29 PM
  3. generating function
    Posted in the Advanced Statistics Forum
    Replies: 3
    Last Post: February 8th 2010, 07:33 AM
  4. Moment generating function and distribution function?
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: January 25th 2009, 02:02 PM
  5. Generating function help plz
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: September 25th 2008, 07:19 AM

Search Tags


/mathhelpforum @mathhelpforum