It can be established that each positive integer is representable as a sum of Fi

Question

It can be established that each positive integer is representable as a sum of Fibonacci numbers, none taken more than once; for example, 5 = F3 + F4, 6 = F1 + F3 + F4, 7 = F1 + F2 + F3 + F4. Write the integers 50, 75, 100, and 125 in this manner. For any prime p not-equal-to 2 or 5, it is known that either Fp-1 or Fp +1 is divisible by p. Confirm this in the case of the primes 7, 11, 13, and 17. From the formula Fn +1 Fn-1 - (-1)n, conclude that consecutive Fibonacci numbers are relatively prime. One can prove that the greatest common divisor of two Fibonacci numbers is also a Fibonacci number; specifically, gcd (Fn, Fm) = Fd, where d = gcd (n, m).

Explanation / Answer

1) 50 = F8 + F7 +F6 + F5 + F4

75 = F9 + F8 + F6 +F5 +F4 + F3 +F2 +F1

100 = F10 + F9 + F6 +F4

125 = F11 + F8 + F7 + F3

3)

For p= 7

F6 = 13 F8=21 which is divisible by 7

For p =11

F10 = 55and F12 =144 So neither Fp-1 =F10 is divisible

For p =13

F12=144 F14=377 F14= 13*29 which is divisible by 13

for p =17

F16= 987 F18=2584 now F18 = 17*152 which is divisible by 13

5) Can be proved

Hint   Put an=1=bn in the much more general result below.

Theorem   If (bn,fn)=1 and fn+1=anfn+bnfn?1 then (fn+1,fn)=(f1,f0).

Proof   Clear if n=0. Else (fn+1,fn)=(anfn+bnfn?1,fn)=(bnfn?1,fn)=(fn?1,fn)=(f1,f0) using induction, and Euclid's Lemma, via the hypothesis that (bn,fn)=1.   QED

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.