Prove that in the Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, ... where each number is the sum of the two previous) there's at least one number that ends in 999999.

I don't know how to prove it, but I think one of the properties of the fibonacci sequence is:

 f(n)² = f(n-1) * f(n+1) +/- 1
where f(n) is the fibonacci sequence, f(1) being the first 1.
It would be +1 if n is odd, and -1 if n is even.

So the f(n) we're looking for has a square of ...000001, which may be one less or one more than the products of f(n-1) and f(n+1).  Let's assume (this isn't necessarily true!) for simplicity that it's one more, so n is odd.

Then, all we need to prove is that there is a pair of consecutive n=even fibonacci numbers whose product is a multiple of 1,000,000.  Is it possible?

Furthermore, for obvious reasons, f(n) is only even if n is divisible by 3.  Therefore, the n we are looking for is not divisible by three, and either f(n-1) or f(n+1) is divisible by 2^6.

Anyway, in conclusion, I'm not sure whether this will actually help or just be something we can look back on and say, "Hey, it does have those properties!"

Posted by Tristan on 2004-06-15 14:58:27