SOLUTION: 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

SOLUTION: 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.

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.

RELATED QUESTIONS
Let {F(n)} = {1,1,2,3,5,8,13,21,34,55,��} be the Fibonacci sequence defined by F(1) = (answered by AnlytcPhil)

The FIbonacci numbers f_n are defined by the equations f_1 = 1, f_2 = 1, f_(n+1) = f_n... (answered by ikleyn)

The Fibonacci sequence, is defined by F_0 = 0, F_1 = 1, and F_n = F_{n - 2} + F_{n - 1}. (answered by CPhill,greenestamps)

Let (Fn)=(1,1,2,3,5,8,13,21,34,55,...) be the fibonacci sequence defined by F1=F2=1,... (answered by venugopalramana)

The function f(n) is defined for all integers n, such that f(x) + f(y) = f(x + y) -... (answered by CPhill,ikleyn)

Let f be a function defined by f(n)=2f(n-1)+3f(n-2), where f(1)=3 and f(2) = 1.... (answered by ikleyn)

A sequence has its first term equal to 4, and each term of the sequence is obtained by... (answered by ikleyn)

F(1)=2... (answered by ikleyn)

The range of the function f: N→N defined by f(x)=... (answered by stanbon,tommyt3rd)

SOLUTION: The Fibonacci numbers f_n are defined by the equations f_1 = 1, f_2 = 1, f_(n+1) =f_n + f_(n&#8722;1) (n &#8805; 2). Prove that gcd(f_(n+1), f_n) = 1 for all natural n.

SOLUTION: 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.