Prove that the gcd of two consecutive Finonacci numbers is 1.

Also identify the ratio of consecutive Fibonacci numbers and try to identify the limit.

- Jun 20th 2008, 11:55 PMmathwizardProve that the gcd of two consecutive Fibonacci numbers is 1.
Prove that the gcd of two consecutive Finonacci numbers is 1.

Also identify the ratio of consecutive Fibonacci numbers and try to identify the limit. - Jun 21st 2008, 12:16 AMIsomorphism
By definition, .

Assume the . This implies and thus . We can thus recursively(or reverse inductively) claim that . Proceeding until n=2, we find that our hypothesis implies

Thus for all positive integers n.

By definition,

If you**prove**that the limit exists, finding it can be easy.

So by definition, .

Let the limit of the ratio be L, then

So .

So solve the quadratic and choose the appropriate root. - Jun 21st 2008, 08:01 PMThePerfectHacker
We can prove something really shocking. Let denote the -th Fibonnaci number. We will prove . WLOG say . Let us apply the Euclidean algorithm to get,

The Euclidean algorithm tells us that if then . It turns out (we will prove this soon) that we have a similar situation with Fibonacci numbers, i.e. . If we assume this fact for now than: . Thus, the problem reduces to computing . This ends up being (we will show this soon) equal to which is in fact by the Euclidean algorithm.

To establish the above facts that we used we need an identity. This identity is for . This is established by using basic induction. With this identity we can prove that if then . This is proven by induction as well: the inductive step is to note and now use induction.

We are now in the position to prove if then (note the fact that will follow since ). By identity we have . But since we know (from above paragraph) that . Therefore, .**If**we can show that then it will mean that . Thus, problem is reduced to proving . Let . Since and (from above) it means . But then it means and . It means since as**Isomorphism**showed. - Jun 21st 2008, 08:34 PMReckoner
- Jun 21st 2008, 11:10 PMNonCommAlg
*this is not related to***mathwizard**'s question, but, i hope, some memebrs find it interesting. anyway ... my apologies for posting

*something off-topic! :)*

i think the most fascinating fact about Fibonacci sequence is that it's periodic modulo any for example Fibonacci sequence

modulo 3 becomes: here repeats in the sequence. so the period is 8.

as far as i know finding a general formula for the period of Fibonacci sequence modulo a given number n is an open problem!! - Jun 22nd 2008, 08:04 AMThePerfectHacker
Consider the equation . There are two solutions, and . This means, . Multiply by to get . Multiply again to get, . Do it again, . The pattern should be clear, . This can of course be fully justified with induction. Likewise, doing it with we get . Subtracting the two equations we get . Thus, . Therefore, . This gives us a formula for computing the Fibonacci ratio.

This is Mine 1:):):):)th Post!!! And my 1:):)th Celebration!!!