Proof that the neighboring Fibonacci numbers are coprime
- Get link
- Other Apps
Hello everyone. Today we will prove that the neighboring Fibonacci numbers are coprime. We will use the method of mathematical induction as a proof method.
Theorem: Let \(F_n \) represent the nth Fibonacci number. Then: \[\forall n \ge 2, \quad \operatorname{NZD} \left (F_n, F_ {n + 1} \right) = 1 \]
Proof:
1. Base case (n = 2)
\[ \operatorname{NZD} \left(F_2, F_{3} \right) = \operatorname{NZD} (1,2) = 1 \]
2. Induction hypothesis (n = m)
Suppose that: \[\operatorname { NZD} \left (F_m, F_ {m + 1} \right) = 1 \]
3. Inductive step (n = m + 1)
Using the assumption from the second step, we will prove that: \[\operatorname{NZD}\left(F_{m+1},F_{m+2}\right)=1\]Since the greatest common divisor of any natural numbers \(a \) and \(b \) is equal to the greatest common divisor of any linear combination of numbers \(a \) and \( b \) we have that \(\operatorname {NZD} (a, b) = \operatorname {NZD} (a, ba) \). With this in mind, we can write the following equation: \[\operatorname {NZD} \left (F_ {m + 1}, F_ {m + 2} \right) = \operatorname {NZD} \left(F_ {m + 1} , F_ {m + 2} -F_ {m + 1} \right) \] Next, by the definition of the Fibonacci sequence \(F_ {m + 2} = F_ {m} + F_ {m + 1} \) we have that: \[\operatorname {NZD} \left (F_ {m + 1}, F_ {m + 2} \right) = \operatorname {NZD} \left (F_ {m + 1}, F_ {m} \right) \] \[\operatorname {NZD} \left (F_ {m + 1}, F_ {m + 2} \right) = \operatorname {NZD} \left (F_ {m}, F_ {m + 1} \right) = 1 \]
\(\blacksquare \)
- Get link
- Other Apps
Comments
Post a Comment