All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
Fibonacci Lore (Posted on 2005-06-10) Difficulty: 4 of 5
The Fibonacci sequence goes F(0)=0, F(1)=1, and for n>1, F(n)=F(n-1)+F(n-2).

Show that for every positive integer m there exists an integer n>0 such that m divides F(n).

See The Solution Submitted by McWorter    
Rating: 4.0000 (3 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
re(3): Proof--Quick fix | Comment 9 of 15 |
(In reply to re(2): Proof--Quick fix by Nick Hobson)

To Nick Hobson:
That's because C was actually referring to a pair of consecutive numbers.  For example, the sequence 1,1,0,1,1,0,... would be ABCABC... where A is (1,1), B is (1,0), and C is (0,1).  I apologize if this was unclear.

To McWorter:
No, my proof does not work for the Lucas sequence, and does not need to.  It consists of two basic steps.

First, I prove that the fibonacci sequence mod m must repeat the same pattern from the beginning over and over.  This is because any pair of consecutive numbers in the sequence necessarily leads to another unique consecutive pair, and is preceded by a unique consecutive pair.  There is a finite number of possible consecutive pairs, so it must repeat at some point.  Since (1,1) is the first pair that appears, it must repeat sometime at a later point.

Second, I prove that if (1,1) is somewhere in the middle of the sequence, it must be preceded by (0,1), for all m.

This does not work for the Lucas sequence, since I can't easily prove that (1,1) is anywhere in the sequence, though I haven't yet disproved it for the Lucas sequence either.

  Posted by Tristan on 2005-06-12 19:30:46

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information