Fibonacci numbers
This post is about an interesting property of the Fibonacci numbers. The Fibonacci numbers, as you know, are entries of the sequence
where any given entry is the sum of the previous two terms. The fifth Fibonacci number is 5, which is 3+2, the sum of the fourth and the third entries. The sixth one is 8, which you get by adding the fifth term to the fourth, etc. If we denote the r^{th} term by , then
You must have seen any number of popular math articles dealing with the Fibonacci numbers and the golden ratio. The golden ratio is the number which is approximately equal to 1.618. If you consider the successive ratios of the Fibonacci numbers you'll see that these ratios approach the golden ratio as you do the computation with larger and larger entries. A math student might prefer to say that tends to as n tends to infinity.
Love a bit of hype? Then you may want to check out this Guardian article, or even better, give a Google search, and check out a few random links. And don't be upset if you find out that you aren't perfect (check out the comment here by Linda)! On a serious note, you could find a lot of intricate patterns among the Fibonacci numbers here.
To warm up to what we are getting at, let's start with the observation that if n divides m, then divides . This isn't hard to be proved. In particular, you see that if n is not a prime number, cannot be a prime either. Mind you, you cannot conclude that is a prime if n is a prime. That's not correct. For instance, 19 is a prime, but
At this point, you may want to have a look at the factorisations of the first few Fibonacci numbers here. As an aside, perhaps I need to add that it's not known "how many" Fibonacci numbers are prime numbers. There could be infinitely many Fibonacci primes, but this is neither proved nor disproved. In general, questions connecting the two basic operations of addition and multiplication are exceedingly difficult. As Heisuke Hironaka, a wellknown Japanese mathematician, put it recently,

[i]f you really think about the relation between addition and multiplication, it's amazingly strange. For instance, 5 is a prime number, but if you add 1, it immediately becomes 6, which is 2 times 3  two different numbers come out. It seems stupid to make a big fuss about it, but if you really think about why multiplication comes up in this strange way, it is very closely related to many [difficult] questions in number theory.
etc. See any pattern? The pattern that you are supposed to see is summarised in the following result.
Result: Let p>5 be a prime number. Let q be any prime dividing . Then p divides either q1 or q+1. Moreover, p divides or .
What follows assumes a bit of undergraduate level math.
Sketch of a proof: Consider the matrix
Observe that
This implies that the order of A in the group divides 4p, where denotes the finite field of q elements. This is because has order 4 modulo q. On the other hand the order of A divides since A is diagonalizable in . Thus the order of A divides the gcd of 4p and . Since p>5, it follows that p divides , which is what we wanted to prove. The second statement easily follows from the first.
P.S: Thanks to froginthewell for an email communication on this topic.
Update (October 18): Professor B. Sury points out that the result can be further strengthened:
Let p>5 be a prime number. Let q be any prime dividing . Then p divides q1 (respectively q+1) when q divided by 5 has remainder 1 or 4 (respectively 2 or 3).
25 Comments:
Interesting article! I'm new to algebra, so here is a question. To say that the order of A divides q^21, isn't it enough to say that the order of GL_2(F_q) is q^21?
Thanks Vishnu. The order of GL_2(F_q) is (q^21)(q^2q). So order of A could possibly be q as well by this argument, which I wanted to avoid.
Oops! I missed the second term. Should be more careful!
Ah, so this is your proof. Nice!
informative blog...
this reminds me the days at college when i used to write computer programs to generate such series...
Thanks froginthewell & Amit.
Interesting post Anand!! There is always something new to learn about teh Fibonacci sequence!
Rahul
I didn't know that about fibonacci and the golden ratio. Interesting to know since the golden ratio is talked about so much since because of it's link to Da Vinci.
Did you know that fibonacci series is commonly found in nature. Ex the arc of a seashell.
I never noticed it till recently. I was at the solar energy decathlon in Washington DC last week.
University of Missouri has incorporated the golden ratio into its solar home design
http://solarhouse.umr.edu/house/design.html
I'm mildly lost, Anand, but never mind! But glad you brought this up. There's so much fascinating stuff about the golden ratio, e and Fibonacci (and yeah Amit, writing code to generate Fibonacci numbers is one of those early programming favourites). Most pleasing rectangles in architecture or art tend to be sized according to the golden ratio. For example, the Parthenon fits almost exactly in a golden ratio.
But we stray from your original subject. Which I'm going back to try to understand.
What I meant to say ... the Parthenon fits almost exactly in a golden rectangle (which is a rectangle whose sides are in the golden ratio).
Dilip, there are skeptics who do not believe that the parthenon fits the golden ratio.
Mario Livio's book The Golden ratio is a good read.
BBC had a series on these special numbers by Simon Singh. You can listen to it here.
Rahul
Rahul  Yes, sth new every time! Thanks for the BBC link and Mario Livio info.
Akshay  Thanks. In early 2004 I had taught 'linear algebra' to a bunch of undergrad eng students. At some point I mentioned Fibonacci numbers. A lot of students enthusiastically talked about Dan Brown. I didn't know who Dan Brown was. Wonder what the students thought about me!
One More Reason  Thanks for the link. I liked that piece.
Dilip  I did not give all the details. But I hope you see the pattern. More when we meet.
Hi Anand
I remember seeing a formula for the Fibonacci number. It took me a half an hour to derive it:
(2/5)*((phi)^m+(1/phi)^m)(1/5)*((1/phi)*phi^mphi*(1/phi)^m)), m=n+1.
I shouldn't be wasting time doing things like this.
Another interesting fact about phi.
phi^n+(1/phi)^n is always an integer. Since (1/phi)<1 this means that phi^n is very close to being an integer for very large n.
just an aside.. Did u go around changing the links to the images that latex generated??.I saw the html code.. all images are in iitb. Does blogger support mathml input?? I have not seen any blogger site use mathml.
Thanks for the nice proof anyway.
Michael  I guess you meant 1/sqrt(5) * (phi^n+(1/phi)^n).
Ashwin  I don't know much about mathml. Never used it myself. Yes, I did change the image codes. I wanted code names that made some sense!
Anand
No, I meant what I wrote. Check it with a calculator or a computer if you have time. It corresponds to another Fibonacci sequence starting with 1 and 3
1,3,4,7,11 etc.
Anand
The formula I gave above for the Fibonacci sequence simplifies to (1/sqrt(5))*(phi^n(1/phi)^n). I guess this is what you meant. I'm sorry.
Thanks Anand, for the suggestion.
I still have to read this proof. Fibonacci nos., interesting stuff.
Hi Anand, it is rather late (19 November!); just saw this page. I thought I should let you know.
Cheers!
Is there any real appication for big fibonachi numbers?

The Number Empire
The statement that each term is the sum of the two preceding terms needs to be qualified
(1) In respect of the first term, ie 1, in that it has no preceding terms and
(2) In respect of the second term,ie 1, in that the statement is correct only if you assume a term of 0 exists prior to the first term of the series displayed.
תיקון טכני
Find Internet Marketing resource hare Online Marketing Strategy  Internet Marketing Tools  Online Marketing Campaign  Online Marketing Business  Online Marketing System  Online Business  Online Home Business  Online Business Tips  Internet Marketing Online
Oes Tsetnoc one of the ways in which we can learn seo besides Mengembalikan Jati Diri Bangsa. By participating in the Oes Tsetnoc or Mengembalikan Jati Diri Bangsa we can improve our seo skills. To find more information about Oest Tsetnoc please visit my Oes Tsetnoc pages. And to find more information about Mengembalikan Jati Diri Bangsa please visit my Mengembalikan Jati Diri Bangsa pages. Thank you So much.
Oes Tsetnoc  Semangat Mengembalikan Jati Diri Bangsa
Post a Comment
<< Home