1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fibonacci nth term

  1. Aug 27, 2012 #1
    I have a doubt regarding its proof. First we assume that solution is of the form x^n-then we solve the quadratic equation and get two values of x-x1 & x2. After that we say solution is of the form ax1^n+bx2^n contradicting our previous assumption that solution is of the form x^n
  2. jcsd
  3. Aug 27, 2012 #2

    Are you assuming we'll be able to guess what you're talking about, what's [itex]\,x_n\,[/itex], what quadratic equation you're talking

    about, etc., or you really think everybody knows this? I mean, I guess you're talking of the quadratic that has the golden mean

    as one of its roots and from which the general term for the n-th Fibonacci element is gotten,. but it'd be nice if you write down

    exactly what's bothering you.

  4. Aug 27, 2012 #3
    Duh, DonAntonio.. its THE Fibonacci nth term proof.
  5. Aug 27, 2012 #4


    User Avatar
    Science Advisor

    It has been a lot of years since we covered this stuff in school...

    The Fibonacci series is an example of a sequence that fits a linear, homogeneous, second-order recurrence relation. That is, each term is expressible as:

    f(n) = k1 * f(n-1) + k2 * f(n-2)

    For the Fibonacci series, k1 = 1 and k2 = 1.

    If one assumes that _a_ solution is f(n) = x^n for some x then one can derive from this the quadratic equation:

    x^2 = x + 1

    Solving this quadratic yields two roots. One is the golden ratio. The other is the negation of the inverse of the golden ratio. And indeed, both roots work as values for x such that x^n fits the given recurrence relation.

    I no longer remember the argument that establishes that these two solutions (and all linear combinations thereof) are the only solutions to the recurrence.
  6. Aug 27, 2012 #5


    User Avatar
    Science Advisor

    Replying to myself.

    One argument is simple: Any particular instance of the Fibonacci series is uniquely determined by its first two terms. Those first two terms also uniquely determine a linear combination of the two solutions that were discovered. It follows that there can be no other solutions.
  7. Aug 27, 2012 #6


    User Avatar
    Science Advisor

    You can also write down the recurrence using a matrix and then diagonalize the matrix.

    This allows you to find the n-th term directly.
  8. Aug 27, 2012 #7
    I'll write down my doubt in detail. Fibonacci series is : an = an-1 + an-2. We assume that solution to this equation is of the form an = xn.
    Substituting we get x2 - x - 1 = 0 and get two values of x say x1 and x2.

    But then we say solution is of the form ax1n + bx2n for some a and b contradicting our previous assumption that solution is xn.
  9. Aug 28, 2012 #8


    User Avatar
    Science Advisor

    I don't think that is how the method is defined. You transform your recursion

    into the quadratic you just described.

    Actually, it seems clear that the answer would not be of the form

    an=xn, since,for one thing, your 1st and 2nd terms are both

    equal to 1.

    EDIT:For some weird reason, I was assumming the x_i were integer-valued. Clearly, they're not, and

    under these conditions, my comments are nonsense. Sorry.
    Last edited: Aug 28, 2012
  10. Aug 28, 2012 #9

    I like Serena

    User Avatar
    Homework Helper

    Hi Avichal! :smile:

    As jbriggs444 already said:

    x1n is a solution of your recurrence relation - without the boundary conditions that the first 2 terms are 1.
    So is x2n.
    And so is any linear combination thereof.

    If you fill in for instance bx2n in the recurrence relation, you should see that it pans out.

    The next step is to find out which linear combination fits with the fact that the first 2 terms are 1.
  11. Aug 28, 2012 #10
    Thank you - its clear now.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook