Prove: The Fibonacci numbers Fi are defined by F0 = 0, F1 = 1, and Fi = Fi_i + F

Question

Prove:

The Fibonacci numbers Fi are defined by F0 = 0, F1 = 1, and Fi = Fi_i + Fi_2 for i 2. Prove the following statements (about the Fibonacci numbers): For positive integers n and i. Fn+i Fn+1Fi (mod Fn). (Hint: The sequence is determined by two consecutive terms. What can you say about F0 and Fn+1 when compared to F0 and F1 modulo Fn.) Use (a) to conclude that, for any positive integer n and k, Fnk = 0 (mod Fn). Use (b) to show that, if m|n, then Fm|Fn. Use above to prove that if Fn is prime, then n is an odd prime or n = 4.

Explanation / Answer

(a)

We shall fix n and prove the result by induction on i.

Clearly the result is true for i = 1 since F_(n+1) = F_(n+1).1 (mod F_n) as F_1 = 1.

Also for i = 2, F_(n+2) = F_(n+1)+F_n = F_(n+1).F_2 + F_n = F_(n+1).F_2 (mod F_n) here we made use of the fact F_2 = 1.

Suppose the result is true for i = 1,...,k for some k>=2.

Then for i = k+1

F_(n+k+1) = F_(n+k)+F_(n+k-1) = F_(n+1).F_k + F_(n+1).F_(k-1) (mod F_n) (by induction hypothesis, note that since k>=2 both k and k-1 are positive integers.Thats why it was important to prove basis step for both i = 1 as well as i = 2).

= F_(n+1).[F_k+F_(k-1)] (mod F_n)

= F_(n+1).F_(k+1) (mod F_n) (fibonacci series property)

hence the result is true for i = k+1.

This completes induction and hence the result since we proved the result for arbitrary n.

(b)

Use induction on k.

Clearly true for k = 1.

Suppose true for k = m.

Then we have F(nm) = 0 (mod F_n)

For k = m+1

F_(nk) = F_(n+nm) = F_(n+1).F_(nm) (mod F_n) = 0 (mod F_n) by induction hypothesis).

Thus by induction the result is true for all positive integers k.

(c)

m|n, say n = km.

Then F_n = F_km = 0 (mod F_m) by part b

Thus F_m divides F_n

(d)

F_n is prime.

Now if m is any positive integer that divides n, then F_m divides F_n (by part c).

Also F_m > 1 for all m > 2, F_m = 1 for m = 1,2. F_m < F_n if m < n (fibonacci series property)

So since F_n is prime it cant have factors other than 1 and F_n.

Thus there cant be m dividing n such that 2 < m < n.

Thus the only divisors of m can be 1,2,n.

Thus n can be prime or 4.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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