# Fibonacci nth term

Avichal
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

DonAntonio
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

Are you assuming we'll be able to guess what you're talking about, what's $\,x_n\,$, 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.

DonAntonio

Diffy
Duh, DonAntonio.. its THE Fibonacci nth term proof.

Homework Helper
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.

Homework Helper
I no longer remember the argument that establishes that these two solutions (and all linear combinations thereof) are the only solutions to the recurrence.

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.

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.

Avichal
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.

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:
Homework Helper
MHB
Hi Avichal!