Proof of Fibonacci Nth Term: Assumptions & Quadratic Eq.

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

 

[jbriggs444]

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.

 

[jbriggs444]

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

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.

 

[Bacle2]

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 : a_n = a_n-1 + a_n-2. We assume that solution to this equation is of the form a_n = xⁿ.
Substituting we get x² - x - 1 = 0 and get two values of x say x₁ and x₂.

But then we say solution is of the form ax₁ⁿ + bx₂ⁿ for some a and b contradicting our previous assumption that solution is xⁿ.

 

[Bacle2]

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

a_n=xⁿ, 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.

 

[I like Serena]

Hi Avichal!

As jbriggs444 already said:

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

If you fill in for instance bx₂ⁿ 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.

 

[Avichal]

Thank you - its clear now.