Let {f_n} denote the Fibonacci sequence. Prove that for every n Let {f_n} denote

Question

Let {f_n} denote the Fibonacci sequence. Prove that for every n

Let {f_n} denote the Fibonacci sequence. Prove that for every n elementof N, gcd (f_n+1, f_n) = 1. (Think about the Euclidean algorithm and/or its ingredients. Use induction. Can you get away with ordinary induction, or do you need strong induction?)

Explanation / Answer

Let Fn and F(n+1) be any two consecutive Fibonacci numbers and suppose there is an integer d > 1 such that d divides Fn and d divides F(n+1). Then F(n+1) - Fn = F(n-1) will also be divisible by d (if d divides a and d divides b, then a = dm and b = dn for some integers m and n. Then a - b = dm - dn = d (m-n), so d divides (a - b) as well). But now notice that Fn - F(n-1) = F(n-2) will also be divisible by d. We can continue this way showing that F(n-3), F(n-4), ... , and finally F1 = 1 are all divisible by d. Certainly F1 is not divisible by d > 1. Thus we have a contradiction to our assumption. Thus it must be the case that Fn and F(n+1) are relatively prime.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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