Zeigen Sie, dass (F_{n+1}, F_{n})= 1 für alle natürlichen n gilt.

Question

Aufgabe:

Sei \( \left(F_{n}\right) \) die Folge der Fibonacci-Zahlen. Zeigen Sie, dass \( \left(F_{n+1}, F_{n}\right)= \) 1 für alle natürlichen \( n \) gilt.

Answer 1

Geht wohl mit vollst. Induktion:

n=1   ggT(F₂,F₁) = ggT(1,1)=1

Wenn es für ein n gilt, also   ggT(F_n+1,F_n) =1, dann folgt

für n+1      ggT(F_n+2,F_n+1)     wegen der Rekursion

             =ggT(F_n+1+F_n,F_n+1)

Nun ist ja ein gemeinsamer Teiler von a+b und a für alle

natürlichen Zahlen auch ein gemeinsamer Teiler von a und b,

also gilt hier ..   =ggT(F_n,F_n+1) = 1 .  q.e.d.