Exercises on the Fibonacci sequence

Exercise 1

Prove that consecutive Fibonacci numbers are relatively prime.

Base case: The first two consecutive Fibonacci numbers are F0 and F1. So the base case is n= 0.

F0= 0 and F1 = 1. So gcd(F0, F1) = gcd(0,1) = 1. So they are relatively prime.

Inductive step: Assuming that consecutive Fibonacci numbers Fn-1 and Fn (where n ≥1) are relatively prime. We need to prove that Fn and Fn+1 are relatively prime.

Fn+1 = 1 ⋅ Fn + Fn-1

Fn = 1 ⋅ Fn-1 + Fn-2

Fn-1 = 1 ⋅ Fn-2 + Fn-3

...

F4 = 1 ⋅ F3 + F2

F3 = 2 ⋅ F2 + 0

Dato che

gcd(Fn+1, Fn) = gcd(Fn, remainder (Fn+1, Fn) )

= gcd(Fn, remainder (Fn-1+Fn, Fn)

= gcd(Fn, Fn-1)

= F2 = 1

Alternate approach

An alternative approach for the inductive step is to use some version of proof by contradiction or contrapositive. For example Suppose that:

Fn and Fn+1 had some common factor d > 1. By the definition of the Fibonacci numbers, Fn + 1 = Fn + Fn - 1. So Fn-1 = Fn + 1 - Fn. So, since d divides both Fn and Fn+1, it must also divide Fn-1. (See facts about divisibility proved in lecture.) But this means that d is a common factor (> 1) of Fn and Fn - 1, so they cannot be relatively prime, contradicting our inductive hypothesis. Assuming a common factor for Fn and Fn+1 led to a contradiction, so they must be relatively prime.

Exercise 2

Si determino i valodi di n per i quali Fn+1/Fn.

Soluzione. Per l'esercizio precendente è chiaro che questi sono n = 1 e n = 2.

Esercizio 3

Si provi che per ogni n e ogni k in ℕ risulta

Fn+k = FkFn+1 + Fk-1Fn F1

se ne deduca che Fkn è un multiplo di Fn.

First obeserve how the relation is derived. Let n ∈ ℕ. We have

Fn+2 = Fn + Fn+1

and iterating this formula we get

Fn+3 = Fn+2 + Fn+1 = Fn + 2Fn+1

Fn+4 = Fn+3 + Fn+2 = 2 Fn + 3Fn+1

...

F2n = FnFn+1 + Fn-1Fn = Fn(Fn+1 + Fn-1)

Solution. Fix k and proceed by induction on n. For n= 1, Formula (F1) becomes

Fk + 1 = Fk + Fk-1

which is true. So, assume the truth of the formula for all 0 ≤ m< n and prove it for n. By the inductive hypothesis we have

Fn-1+k = FkFn + Fk-1Fn-1

and

Fn -2+k = Fk Fn-1 + Fk-1 Fn-2

hence, summing, we get

Fn+k = Fn-1+k + Fn-2+k = Fk(Fn+Fn-1) + Fk-1 (Fn-1 + Fn-2) = FkFn+1 + Fk-1 Fn

We want to prove now that Fkn is a multiple of Fn. Proceed by induction on k. For k = 1 this is obvious. Assume that Fmn is a multiple of Fn for all m ≤ k and prove it for k + 1. The previous relation implies

F(k+1)n = Fkn+n = FknFn+1 + Fkn-1Fn

so, by the inductive hypothesis, both Fn and Fkn are multiples of Fn, so F(k+1)n is too.

Esercizio 4

Prove that the greatest common divisor of two Fibonacci numbers is again a Fibonacci number.Precisely

gcd(Fn, Fm) = Fd,   d = gcd(m,n)

For example, if m = 14 and n = 21, then gcd(f14,f21) = gcd(377,10946) = 13 and fgcd(14,21)=f7= 13.

Proof

  1. We first write n = mk + r, where r < m, and then fn = fmk + r

  2. From relation F1 we have fn = fmk + r = fmk+1* fr + fmk*fr-1

  3. And then when taking the gcd(fm, fn) = gcd(fm, fmk+1* fr + fmk*fr-1)

  4. The next step, we can drop the fmk*fr-1 sum, because fm|fmk and lemma 1. We get gcd(fm, fn) = gcd(fm, fmk+1*fr)

  5. And for the last step we use lemma 3, because gcd(fm, fmk+1) = 1 (this follows from lemma 2). So we get gcd(fm, fn) = gcd(fm, fr)

±
«Defective Verbs Index Esercizi Successione di Fibonacci»