Results 1 to 8 of 8

Math Help - Finding Explicit formula for a recursion

  1. #1
    Newbie
    Joined
    Dec 2010
    Posts
    5

    Finding Explicit formula for a recursion

    how would one go about finding the explicit formula for a_n = 2a_(n-1) - a_(n-3) given a_1=2, a_2=3, a_3=5?

    Please help, need to get answer quickly! Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Do you know the characteristic equation method of solving recurrences?

    Rewrite the recurrence as a_n - 2a_(n-1) + a_(n-3) = 0
    Characteristic equation is r^3 - 2r^2 + 1 = 0
    Find all solutions for r.
    You should find 3 different roots r_1, r_2, r_3.

    Your final formula is a_n = A*r_1^n + B*r_2^n + C*r_3^n

    Now use the initial conditions to find A, B, and C.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2010
    Posts
    193
    See if you can prove, perhaps by induction, that this is really just the Fibonacci sequence (without the initial 0,1,1). Then I suppose it's a question of an exact formula for the Fibonacci numbers.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.

    [Never mind]
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    193
    Quote Originally Posted by snowtea View Post
    Is it fibonnacci? Because inital sequence 1,3,5 is already not Fibonnaci.
    The initial sequence is 2,3,5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Dec 2010
    Posts
    470
    Yeah, your right. I must be dislexic today.
    That's what happens when they don't latexify their mathematics

    Your right, it does look like Fibonnaci. I think it is because a_(n-1) - a_(n-3) = a_(n-2) for this set of initial conditions.
    Note the recurrence is only Fibonnaci because of the initial conditions provided. Given numbers like 1,2,5 it will no longer be Fibonnaci.

    But still the explicit formula for Fibonnaci is quite ugly
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Nov 2010
    Posts
    193
    Quote Originally Posted by snowtea View Post
    Yeah, your right. I must be dislexic today.
    That's what happens when they don't latexify their mathematics

    Your right, it does look like Fibonnaci. I think it is because a_(n-1) - a_(n-3) = a_(n-2) for this set of initial conditions.
    Note the recurrence is only Fibonnaci because of the initial conditions provided. Given numbers like 1,2,5 it will no longer be Fibonnaci.

    But still the explicit formula for Fibonnaci is quite ugly
    Well... I doubt as if he will find a simpler one. If there were a simpler one, then... well, it would.. already.. be simpler.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    Dec 2010
    Posts
    5
    problem solved, thanks for all the responses
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: October 30th 2010, 10:37 AM
  2. Help Finding Explicit Formula and Error Bound
    Posted in the Advanced Math Topics Forum
    Replies: 2
    Last Post: October 30th 2010, 08:27 AM
  3. explicit formula
    Posted in the Algebra Forum
    Replies: 2
    Last Post: November 19th 2008, 12:23 PM
  4. Finding the explicit formula and the 100 term
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 26th 2007, 08:53 PM
  5. Determine r for Explicit Formula
    Posted in the Calculus Forum
    Replies: 1
    Last Post: October 13th 2007, 02:37 PM

/mathhelpforum @mathhelpforum