What non-zero Fibonacci numbers are one less than a power of two? (That would make each of them consist of all 1's in binary.)

The function that defines the Fiboncacci series is:

f(n) = (1/√5) ((1+√5)/2)^n - (1/√5) ((1-√5)/2)^n

Why?

The series is is defined as f(n+2) = f(n+1) + f(n)

Let's say f(n) = Ae^(kn)  (which should be true if we can turn the series into a continuous function)

f(n+2) = f(n+1) + f(n)
Aek^(k(n+2)) = Ae^(k(n+1)) + Ae^(kn)
Ae^(kn) * e^(2k) = Ae^(kn) * e^k + Ae^(kn)

Dividing by Ae^(kn) we get:

e^(2k) = e^k + 1 or (e^k)^2 - e^k - 1 = 0

Using the quadratic formula:

e^k = (1 ± √(1+4))/2

Seing as f(n) = Ae^(kn) = A (e^k)^n = A ((1 ± √5)/2)^n

= A ((1 + √5)/2) - A ((1 - √5)/2)

A is 1/√5 simply because it's the conjugate.


I hope that helps =)

Posted by George on 2007-01-22 17:59:09