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.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


<pre>
Let us assume that  gcd({{{f[n+1]}}},{{{f[n]}}}) = d  is positive integer greater than 1.

Then both  {{{f[n+1]}}}  and  {{{f[n]}}}  are divisible by d.

Since  {{{f[n+1]}}} = {{{f[n]}}} + {{{f[n-1]}}}  by the definition, then {{{f[n-1]}}} is divisible by d.

In turn, since  {{{f[n]}}} = {{{f[n-1]}}} + {{{f[n-2]}}}  by the definition, then {{{f[n-2]}}} is divisible by d.

Moving back step by step, we then conclude that the entire chain (sequence) {{{f[n+1]}}}, {{{f[n]}}}, {{{f[n-1]}}}, {{{f[n-2]}}}, . . . , {{{f[2]}}}  consists 

of integers divisible by  d.  But  {{{f[2]}}} = 1  and  {{{f[3]}}} = 2  are relatively prime and have no common divisor.

This contradiction proves that our starting assumption was wrong. Hence,   gcd({{{f[n+1]}}},{{{f[n]}}}) = 1  for all natural n.

QED.


  //This type of proving is called  <U>a proof by descent</U>. 
</pre>