Sunday, October 16, 2005

Fibonacci numbers

This post is about an interesting property of the Fibonacci numbers. The Fibonacci numbers, as you know, are entries of the sequence

1,1,2,3,5,8,13,21,34,55,89,144,...,

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 rth 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 well-known 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.
In any case, let's focus on the Fibonacci numbers at the prime positions. So have a look at the factorisations here. To avoid a few initial exceptions, I'm going to start looking at primes p>5 onwards. Now


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 q-1 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 e-mail 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 q-1 (respectively q+1) when q divided by 5 has remainder 1 or 4 (respectively 2 or 3).

23 Comments:

At 10:30 AM, Anonymous Anonymous said...

Interesting article! I'm new to algebra, so here is a question. To say that the order of A divides q^2-1, isn't it enough to say that the order of GL_2(F_q) is q^2-1?

 
At 11:23 AM, Anonymous Anonymous said...

Thanks Vishnu. The order of GL_2(F_q) is (q^2-1)(q^2-q). So order of A could possibly be q as well by this argument, which I wanted to avoid.

 
At 11:49 AM, Anonymous Anonymous said...

Oops! I missed the second term. Should be more careful!

 
At 12:40 PM, Blogger froginthewell said...

Ah, so this is your proof. Nice!

 
At 4:22 PM, Blogger Amit Bulbule said...

informative blog...

this reminds me the days at college when i used to write computer programs to generate such series...

 
At 11:00 PM, Anonymous Anonymous said...

Thanks froginthewell & Amit.

 
At 3:11 AM, Blogger Iyer the Great said...

Interesting post Anand!! There is always something new to learn about teh Fibonacci sequence!

Rahul

 
At 5:59 AM, Blogger Unknown said...

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.

 
At 7:38 PM, Blogger Riot said...

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

 
At 11:11 PM, Blogger Dilip D'Souza said...

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.

 
At 11:13 PM, Blogger Dilip D'Souza said...

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

 
At 1:06 AM, Blogger Iyer the Great said...

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

 
At 1:48 AM, Blogger Anand said...

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.

 
At 3:13 AM, Blogger Michael Higgins said...

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^m-phi*(-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.

 
At 12:31 PM, Blogger Aswin said...

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.

 
At 9:37 PM, Anonymous Anonymous said...

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!

 
At 9:57 AM, Blogger Michael Higgins said...

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.

 
At 10:03 AM, Blogger Michael Higgins said...

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.

 
At 7:51 AM, Anonymous Anonymous said...

Thanks Anand, for the suggestion.

I still have to read this proof. Fibonacci nos., interesting stuff.

 
At 7:24 AM, Blogger Abi said...

Hi Anand, it is rather late (19 November!); just saw this page. I thought I should let you know.

Cheers!

 
At 2:42 AM, Blogger WEBQC said...

Is there any real appication for big fibonachi numbers?





-------------------
The Number Empire

 
At 4:32 AM, Blogger john o'callaghan said...

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.

 
At 12:38 PM, Anonymous Anonymous said...

תיקון טכני

 

Post a Comment

<< Home