Results 1 to 3 of 3

Math Help - Recursion and Closed Formulas

  1. #1
    Newbie
    Joined
    Jul 2009
    Posts
    18

    Recursion and Closed Formulas

    Hello!

    I've be scanning different help forums and I have a come across two different questions involving finding closed formulas. I have attempted to answer them with no luck and now I am curious of the answer.

    The questions are --> Find a closed formula for the sequence:

    a) 0,1,3,0,1,3,0,1,3,0,1,3,0,.... where a0 = 0, a1 = 1, a2 = 2, a3 = 0,...

    b) an = an-1 + 3an-2, where a0 = 0 and a1 = 1

    Perhaps one of you could shed some light on these questions. I appreciate your time. Thank you in advance!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Feb 2010
    From
    Rez
    Posts
    21
    For the first one, I'd do it with generating functions - the generating function for  0 + 1x + 3x^2 + 0x^3 + 1x^4 + 3x^5 + ... is \frac {x + 3x^2}{1-x^3}.
    So  a_n = [x^n] \frac {x + 3x^2}{1-x^3} . By that I mean the coefficient of x^n in the sequence generated by \frac {x + 3x^2}{1-x^3} .

    The second one is just a regular homogeneous recursion. Find the characteristic polynomial ( x^2 - x - 3 ). Find its roots: these are  \frac {1 \pm \sqrt{13}}{2} . Then solve the system:
    a_0 = 0 = x + y
    a_1 = 1 = x(\frac {1 + \sqrt{13}}{2}) + y(\frac {1 - \sqrt{13}}{2}) .
    The closed formula is  a_n = x(\frac {1 + \sqrt{13}}{2})^n +  y(\frac {1 - \sqrt{13}}{2})^n .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jul 2009
    Posts
    18
    Thanks!

    If you don't mind me asking, were you able to come up with a closed formula for the sequence generated by (x + 3x^2)/(1-x^3) .

    I've tried splitting it up until different series and simplfying with no luck. I have a feeling the closed formula will involve complex numbers, but at the moment I have only found formulas that work for a0, a3, a6, etc.. (where the coefficient is 0.

    For example--> (([-1 + i*sqrt(3)]/2)^n) - (([-1 - i*sqrt(3)]/2)^n)

    Any ideas anyone?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Closed Form of a Recursion with a Sqared Term
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 16th 2010, 02:48 PM
  2. Proof: recursive and closed formulas
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 28th 2010, 06:49 PM
  3. Metric Space, closed sets in a closed ball
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: November 19th 2009, 06:30 PM
  4. Closed Linear Operators/Closed Graph Theorem
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: June 17th 2009, 03:36 AM
  5. Continuity & inverse image of closed sets being closed
    Posted in the Differential Geometry Forum
    Replies: 5
    Last Post: March 9th 2009, 06:07 PM

Search Tags


/mathhelpforum @mathhelpforum