Results 1 to 5 of 5

Math Help - Convert Recursive to Closed Formula

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    Australia
    Posts
    4

    Convert Recursive to Closed Formula

    I have a sequence defined by the following recursive formula:
    T_n = T_{n-1} \times 2 - T_{n-10}

    This produces the sequence:
    n = 1 to 10: 1, 1, 2, 4, 8, 16, 32, 64, 128, 256
    n = 11 to 15: 511, 1021, 2040, 4076, 8144

    note: n=1 is an anomaly.

    I need help converting the formula to a closed form. The closed formula doesn't have to reproduce the above sequence for the n = 1 to 10 parts if it makes it any easier. I can account for those special cases in my program.
    Last edited by s4276560; April 12th 2012 at 07:43 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Convert Recursive to Closed Formula

    2^{n-2}-(n-9)2^{n-12}?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2012
    From
    Australia
    Posts
    4

    Re: Convert Recursive to Closed Formula

    That answer works from n = 11 to 20, but fails beyond that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2008
    From
    UK
    Posts
    484
    Thanks
    65

    Re: Convert Recursive to Closed Formula

    Sorry. I knew it couldn't be that easy really. The characteristic polynomial only has one root that's nice to work with:

    1.998029470262286698....

    Beyond a certain point your sequence is probably almost indistinguishable from a GP. Using some term, m say, of your sequence you can generate others using T_n= nearest integer to T_m*1.998.....^{n-m}

    I hope I'm not wrong again. I could check but I'm sure you will.

    Any experts reading this thread?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Apr 2012
    From
    Australia
    Posts
    4

    Re: Convert Recursive to Closed Formula

    @a tutor> Thanks for your help. After researching & trialing different methods, I gave up trying to find the closed form using Linear Homogeneous Recurrence Relation ​like you suggested. Instead, I am now using Transitional Matrix.

    My original intent for finding the closed form was for efficiency for very large values of n, but I found that transitional matrix works surprisingly efficiently as well.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof: recursive and closed formulas
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: February 28th 2010, 05:49 PM
  2. Recursive formula find closed something
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: February 28th 2010, 01:32 AM
  3. Replies: 5
    Last Post: February 22nd 2010, 01:41 PM
  4. Find Closed Form given Recursive Formula
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 3rd 2009, 12:52 PM
  5. Converting Closed Form to Recursive Formula
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: January 20th 2009, 01:38 PM

Search Tags


/mathhelpforum @mathhelpforum