Results 1 to 7 of 7

Thread: generating function for sequence question

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    55

    Question generating function for sequence question

    Consider the sequence $\displaystyle (a_n)_{n\ge 0}$ defined by the following recurrence

    $\displaystyle a_0 = 2, a_{n+1} = 4a_n + 5, \forall n \ge 0.$

    Let $\displaystyle f(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = a_0+a_1z+a_2+z^2+.... $ be the gernerating function for the sequence.
    Express f(z) as a rational function.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    The solution of the difference equation $\displaystyle a_{n+1}= 4\ a_{n} + 5$ with the 'initial condition' $\displaystyle a_{0}=2$ is...

    $\displaystyle a_{n} = 2^{2n+1} +5\ n$ (1)

    ... so that is...

    $\displaystyle \displaystyle f(z)= \sum_{n=0}^{\infty} (2^{2n+1}+ 5\ n)\ z^{n}$ (2)

    Now we consider separately the terms of (2)...

    $\displaystyle \displaystyle \sum_{n=0}^{\infty} 2^{2n+1} z^{n} = 2\ \sum_{n=0}^{\infty} (4z)^{n} = \frac{2}{1-4\ z}$ (3)

    $\displaystyle \displaystyle \sum_{n=0}^{\infty} 5\ n\ z^{n} = 5\ \sum_{n=0}^{\infty} n\ z^{n} = 5\ z\ \sum_{n=1}^{\infty} n\ z^{n-1} = 5\ z\ \frac{d}{dz} \frac{1}{1-z} = \frac{5\ z}{(1-z)^{2}}$ (4)

    ... so that the series (2) converges for $\displaystyle |z|<\frac{1}{4}$ and is...

    $\displaystyle \displaystyle f(z)= \frac{2}{1-4\ z} + \frac{5\ z}{(1-z)^{2}}$ (5)

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2008
    Posts
    55
    Thanks so much for your reply chisigma!

    How did you get equation 1 though?

    I have been looking for tutorials online for "difference equation" and not making much sense of it.

    For eg. If its a similar question with a different sequence

    $\displaystyle 2a_{n+2} = 9a_{n+1} + 5a_n$

    $\displaystyle a_0 = 0, a_1 = 11$

    $\displaystyle \forall n \geq 0$

    How would you equate the "difference equation"

    Thanks again
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,774
    Thanks
    2823
    Awards
    1
    Quote Originally Posted by smplease View Post
    Thanks so much for your reply chisigma!
    How did you get equation 1 though?
    Actually there is mistake in $\displaystyle \chi\sigma$'s equation (1).
    You can use this website to see the correct answer.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Mar 2008
    Posts
    55
    Is there a function that can be used to find this answer?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    A great 'Thank You' to Plato for having found my mistake... a mistake caused by my superficiality ...

    If we have a linear first order difference equation of the form...

    $\displaystyle \displaystyle a_{n+1}= \alpha_{n}\ a_{n} + \beta_{n}$ , $\displaystyle \a_{0}= a$ (1)

    ... its solution is...

    $\displaystyle \displaystyle a_{n}= p_{n}\ (a + \frac{\beta_{0}}{p_{1}} + \frac{\beta_{1}}{p_{2}} + ... + \frac{\beta_{n-1}}{p_{n}})$ (2)

    ... where $\displaystyle \displaystyle p_{n}= \prod_{k=0}^{n-1} \alpha_{k}$ . In this case the difference equation is...

    $\displaystyle \displaystyle a_{n+1}=4\ a_{n} +5$, $\displaystyle a_{0}=2$ (3)

    ... so that is $\displaystyle \alpha_{n}=4=2^{2}$, $\displaystyle \beta_{n}= 5$ and $\displaystyle a=2$ and the solution of (3) is...

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

    The first term was correct and the same is for its contribution to $\displaystyle f(z)$... the contribution of the second term has to be evaluated...

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    6
    The contribution of the second term is easy to find because is...

    $\displaystyle \displaystyle \sum_{n=0}^{\infty} (2^{2n}-1)\ z^{n} = \sum_{n=0}^{\infty} (4z)^{n} - \sum_{n=0}^{\infty} z^{n} = \frac{1}{1-4z} - \frac{1}{1-z}$ (1)

    ... so that...

    $\displaystyle \displaystyle f(z)= \frac{\frac{11}{3}}{1-4z} - \frac{\frac{5}{3}}{1-z}$ (2)

    Kind regards

    $\displaystyle \chi$ $\displaystyle \sigma$
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. closed form for sequence z=z^2+c & generating function
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: Oct 4th 2011, 03:05 AM
  2. Generating function for a sequence
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Apr 27th 2011, 10:16 AM
  3. Generating Function Application Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Dec 15th 2010, 07:25 PM
  4. moment generating function question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: Nov 23rd 2010, 02:37 AM
  5. last generating function question.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 5th 2009, 05:51 PM

Search Tags


/mathhelpforum @mathhelpforum