Are there Fibonacci numbers which are also powers of 2, other than the obvious ones?
The sequence of Fibonacci numbers begins
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
where each number is the sum of the two previous ones. By some tortuous chain of logic I found myself wondering if any of them are powers of two, other than the obvious ones (1, 1, 2, 8).
It seems like there shouldn't be, because both sequences are exponentially sparse. The number of Fibonacci numbers in [2n, 2n+1-1] is at most two. So the "probability" that 2n is Fibonacci is at most 2/2n, since there are 2n integers in this interval; if we sum this over n it converges, so we expect there to be finitely many, and the exponential decay seems to indicate that those Fibonacci numbers which are powers of two should appear early.
Now, it turns out that a positive integer z is a Fibonacci number if and only if one of 5z2 + 4 and 5z2 - 4 is a perfect square. I learned this from Wikipedia, which gets it from a 2007 book by Alfred Posamentier and Ingmar Lehmann entitled The (Fabulous) FIBONACCI Numbers. So the question is equivalent to asking which numbers that are five times a power of four, plus or minus four, are perfect squares. That is, if one of 5(4n) + 4 and 5(4n) - 4 is a perfect square, then 2n is a Fibonacci number, and conversely. We have 5(40) + 4 is a square, as is 5(41) + 4 and 5(43) + 4; these are 9, 25, and 324 respectively.
By looking at the Fibonacci numbers modulo 8, we see that multiples of 8 occur exactly in positions which are divisible by 6 -- the sixth, twelfth, ... Fibonacci numbers are the only multiples of 8. The "plus or minus" in the previous paragraph seems to depend on the parity of the position -- a Fibonacci number z occuring in an even position has 5z2 + 4 a perfect square, and a Fibonacci number occuring in an odd position has 5z2 - 4 a perfect square. Powers of two have to occur in even positions (they're multiples of eight) and so we're looking for positive integers n such that 5(4n) + 4 is a perfect square; then 2n will be a Fibonacci number.
It might also be interesting to look at when the first Fibonacci number which is divisible by 2n appears. (This is related to, but not the same as, the Pisano period, which is the period of the Fibonacci numbers modulo some integer.) If 2n is a Fibonacci number, it is the first Fibonacci number divisible by 2n.
Does someone who's better at number theory than I am want to finish this?
Edit (3:43 pm): Stregatto points out that my implicit conjecture that 1, 2, 8 are the only Fibonacci numbers which are powers of two is true, and is a consequence of Carmichael's theorem for Fibonacci numbers.
Subscribe to:
Post Comments (Atom)
4 comments:
Only every third Fibonacci number is relevant, because the rest are odd. But from the identity
F_{3n} = F_n (5 F_n^2 + 3(-1)^n))
we see that if F_n isn't a power of two, then neither is F_{3n}. QED.
Slight type on your post... 5(4^1)+4 isn't 25 it's 24 (not square). However, 5(4^1)-4 is 16, which is square.
An even more powerful resul is true: with the exceptions of 1, 8 and 144 (F_0 = F_1, F_6 and F_12) every Fibonacci number has a prime factor that is not a factor of any smaller Fibonacci number (Carmichael's theorem). From this theorem it follows immediately that there can be no other power of two other than 1,2,8.
To prove it by extending your reasoning, I think you can change it from 5(4^n)+4 = k^2 to 5(4^n) = k^2 - 4 = (k-2)(k+2). Then one of (k-2) or (k+2) is of the form 5(4^i) and the other is (4^j). I think that will give you that n = i + j is either 0, 1 or 3.
Post a Comment