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.
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.
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.
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.
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!!
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 1th Post!!! And my 1th Celebration!!!