Results 1 to 7 of 7

Math Help - generating function for sequence question

  1. #1
    Junior Member
    Joined
    Mar 2008
    Posts
    55

    Question generating function for sequence question

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

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

    Let  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
    5
    The solution of the difference equation a_{n+1}= 4\ a_{n} + 5 with the 'initial condition' a_{0}=2 is...

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

    ... so that is...

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

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

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

    \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 |z|<\frac{1}{4} and is...

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

    Kind regards

    \chi \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

    2a_{n+2} = 9a_{n+1} + 5a_n

    a_0 = 0, a_1 = 11

    \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
    18,824
    Thanks
    1717
    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 \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
    5
    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 a_{n+1}= \alpha_{n}\ a_{n} + \beta_{n} , \a_{0}= a (1)

    ... its solution is...

    \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 p_{n}= \prod_{k=0}^{n-1} \alpha_{k} . In this case the difference equation is...

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

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

    \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 f(z)... the contribution of the second term has to be evaluated...

    Kind regards

    \chi \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
    5
    The contribution of the second term is easy to find because is...

    \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 f(z)= \frac{\frac{11}{3}}{1-4z} - \frac{\frac{5}{3}}{1-z} (2)

    Kind regards

    \chi \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: October 4th 2011, 03:05 AM
  2. Generating function for a sequence
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 27th 2011, 10:16 AM
  3. Generating Function Application Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 15th 2010, 07:25 PM
  4. moment generating function question
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: November 23rd 2010, 02:37 AM
  5. last generating function question.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2009, 05:51 PM

Search Tags


/mathhelpforum @mathhelpforum