Berechnen Sie für n ∈ {3,4,5,6} den ggT( F_n , F_n+1 ) und stellen Sie diesen als a F_n + b F_n+1 dar, d.h.

Question

Seien für n > 0 die Zahlen $F_n$ die Fibonacci-Zahlen so definiert:

Die Fibonacci-Zahlen $F_n$ sind rekursiv definiert durch:

1.) Man setzt: $F_0$:= 1 und $F_1$:= 1

2.) Für n ∈ ℕ, n > 1setzt man: $F_n = F_{n-1} + F_{n-2}$

a) Berechnen Sie für n ∈ {3,4,5,6} den ggT($F_n$ , $F_{n+1}$) und stellen Sie diesen als $a F_n + b F_{n+1}$ dar, d.h. finden Sie Zahlen a,b, so dass ggT$\left( F_n ,\, F_{n+1}\right) = a F_n + bF_{n+1}$ gilt.

b) Stellen Sie für allgemeines n >= 3 eine Vermutung über a und b auf und beweisen Sie diese.