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
We first write n = mk + r, where r < m, and then fn = fmk + r
From relation F1 we have fn = fmk + r = fmk+1* fr + fmk*fr-1
And then when taking the gcd(fm, fn) = gcd(fm, fmk+1* fr + fmk*fr-1)
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)
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)