Beweis durch vollständige Induktion: Fibonacci-Zahlen

Question

die Aufgabe lautet:

Die Fibonacci-Folge {x_k} ist durch
x₁ :=1, x₂ :=1, x_k :=x_k−1 +x_k−2
rekursiv definiert. Zeigen Sie mittels vollständiger Induktion, dass x_3n eine gerade Zahl für alle n ∈ N ist.

Also muss ich zeigen dass : x_3n-1 + x_3n-2 = 2n. Richtig?

Induktionsanfang: n=1

x2+x1= 2     2=2 Wahr.

Induktionsschritt:

ZZ:  x_3n+2 + x_3n+1 = 2n + 2

Ich habe das versucht aber gehe immer wieder zum selben Punkt und kann nicht weiter. Bitte Hilfe

Vielen Dank im voraus!

Answer 1

IA: \( x_3 = 2 \) ist gerade

IS:

$$ x_{3n+3} = x_{3n+2}+x_{3n+1} = (x_{3n+1}+x_{3n})+x_{3n+1} = 2x_{3n+1}+x_{3n} $$

Nach IV ist \( x_{3n} \) durch 2 teilbar, also auch \( x_{3n+3} \).

Answer 2

Du musst zeigen: Aus x_3n gerade folgt x_3(n+1) gerade. Zunächst ist folgender Satz zu beweisen:

Da weder alle Fibonacci-Zahlen gerade noch alle ungerade sind, ist Ihre Folge u, u, g, u, u, g, ....

x_3n gerade (Voraussetzung)

x_3n+1 und x_3n+2 ungerade (Satz)

x_3n+3=x_3(n+1)  ungerade (Satz).