Thread: Number sequence help

  1. #1
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218

    Number sequence help

    Say I have the following recursive numbersequence: a(n) = a(n-1)+2a(n-2)

    I know that a(1) = 2 and I know that a(2) = 3. Now I need to find an explicit formula for that.

    I know it has something to do with fibonaccis sequence since, if a(1)=1 and a(2) = 1 the explicit formula would have been a(n) = (2^n-(-1)^n)/3. The problem that this does not work when a(1) = 2 and a(2) = 3.

    Can anybody explain how I should come up with an explicit formula for this problem?
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  2. #2
    5|-|1+|-|34|) ober's Avatar
    Join Date
    Aug 2001
    Posts
    4,429
    The answer..... is 42.

  3. #3
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    herrrrrrrrrrrm.......ummmmmmmmm.......no
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    It can be solved with matrices. I'll see if I can produce some images for you.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    That would be very nice!!
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  6. #6
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    OK, the board is semi-down right now, so we'll see if this gets through..


    I'm going to assume that you know how to handle matrices. First, we'll define a matrix A like this:
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  7. #7
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Ahh, the boards are back!


    Now, we add your recursive formula:
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  8. #8
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    Ok....yah I know how to handle matrices (at least to the point where I can multiply them).
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

  9. #9
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    We want to diagonalize X, to make it easy to calculate X^n.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  10. #10
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    When we perform the last multiplication with A2, the first row of the result will be a(n+2).

    Here's the final formula:
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  11. #11
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Numbers generated from this formula:

    3 7 13 27 53 107 213 427 853 1707 3413 6827 13653 27307 54613 109227 218453 436907 873813 1747627 3495253

    Seems correct for the first three, at least. HTH
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  12. #12
    Registered User
    Join Date
    Aug 2003
    Posts
    1,218
    That definately seems to be correct! Thanks a bunch, now I just have to get a good grip on everything but that shouldnt be too hard... ! Thanks.

    It is correct for the 18 first numbers.
    Last edited by Shakti; 05-26-2005 at 08:52 AM.
    STL Util a small headers-only library with various utility functions. Mainly for fun but feedback is welcome.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. scanf oddities
    By robwhit in forum C Programming
    Replies: 5
    Last Post: 09-22-2007, 01:03 AM
  2. number sequence
    By valleyboy in forum C Programming
    Replies: 1
    Last Post: 05-01-2005, 02:24 PM
  3. Prime number program problem
    By Guti14 in forum C Programming
    Replies: 11
    Last Post: 08-06-2004, 04:25 AM
  4. parsing a number
    By juancardenas in forum C Programming
    Replies: 1
    Last Post: 02-19-2003, 01:10 PM
  5. Random Number problem in number guessing game...
    By -leech- in forum Windows Programming
    Replies: 8
    Last Post: 01-15-2002, 05:00 PM