Results 1 to 5 of 5

Thread: Ordinary generating function

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

    Ordinary generating function

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

    $\displaystyle c_{n}x^{n}=3c_{n-1}x^{n}+3^{n}x^{n}$

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

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

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

    2nd term $\displaystyle \sum_{n\geq1}3^{n}x^{n}=$$\displaystyle \left(\sum_{n\geq0}3^{n}x^{n}\right)-1
    $
    So $\displaystyle h(x)-1=3xh(x)+\frac{1}{1-3x}-1$; $\displaystyle \left(1-3x\right)h(x)=\frac{1}{1-3x}$ And $\displaystyle 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 $\displaystyle 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
    12,028
    Thanks
    848
    Hello, oldguynewstudent!

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


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


    Therefore: .$\displaystyle 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 $\displaystyle h(x)=\frac{1}{(1-3x)^2}$.

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

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

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

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

    We see that $\displaystyle c_n=n 3^{n-1}$ for $\displaystyle n=2, 3, 4, \ldots$ (You can shift the index by one to get book's solution.)
    Last edited by roninpro; Jul 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

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

    write

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

    then use it on the equation

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

    so

    $\displaystyle \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 $\displaystyle f(n)=3^n(n+1)$.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    255
    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: Jul 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: Feb 8th 2010, 07:33 AM
  4. Moment generating function and distribution function?
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: Jan 25th 2009, 02:02 PM
  5. Generating function help plz
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: Sep 25th 2008, 07:19 AM

Search Tags


/mathhelpforum @mathhelpforum