Prove By Induction (Fibonacci Sequence)

Question

Prove by PMI $\gcd(f_n,f_{n+1}) = 1$ for all natural numbers $n$. $f_n$ represents the Fibonacci sequence.

score 2 · Answer 1 · answered Oct 22 '14 at 12:49

2

Three consecutive terms in a Fibonacci sequence can be written as $a,b,a+b$. If $d$ divides $b$ and $d$ divides $a+b$, then $d$ divides $a+b-b=a$.

answered Oct 22 '14 at 12:49

please delete me

score 1 · Answer 2 · answered Oct 22 '14 at 12:48

1

Hint: $\gcd(a,b)=\gcd(a-b,b)$.

answered Oct 22 '14 at 12:48

Hagen von Eitzen

How can you prove this. – George J. Adams Oct 22 '14 at 12:58
@Ron.J.Adams By applying any of the definitions of $\gcd$ or one step of the Euclidean algorithm – Hagen von Eitzen Oct 22 '14 at 13:01
Can you show me how? – George J. Adams Oct 22 '14 at 13:05

2 Answers2