Question 1030238: The Fibonacci numbers f_n are defined by the equations f_1 = 1, f_2 = 1, f_(n+1) =f_n + f_(n−1) (n ≥ 2). Prove that gcd(f_(n+1), f_n) = 1 for all natural n.
Answer by ikleyn(53937)   (Show Source):
You can put this solution on YOUR website! .
The Fibonacci numbers f_n are defined by the equations f_1 = 1, f_2 = 1, f_(n+1) =f_n + f_(n−1) (n ≥ 2).
Prove that gcd(f_(n+1), f_n) = 1 for all natural n.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Let us assume that gcd( , ) = d is positive integer greater than 1.
Then both and are divisible by d.
Since = +  by the definition, then is divisible by d.
In turn, since = +  by the definition, then is divisible by d.
Moving back step by step, we then conclude that the entire chain (sequence) , , , , . . . ,  consists
of integers divisible by d. But = 1 and  = 2 are relatively prime and have no common divisor.
This contradiction proves that our starting assumption was wrong. Hence, gcd(,) = 1 for all natural n.
QED.
//This type of proving is called a proof by descent.
| |
|
